clojure - 为什么字符集看起来是有序的？

Question

我一直认为集合没有排序，但注意到字符集确实似乎是有序的:

(seq #{\e \c \b \z \a}) 

=> (\a \b \c \e \z)

如果我引入其他类型的字符，似乎它们是根据字符代码排序的:

(seq #{\e \A \c \space \b \z \a})

=> (\space \A \a \b \c \e \z)

为什么字符根据其代码排序，但数字集似乎具有任意顺序？

Answer 1

这是因为 Character/hashCode 直接与字符的序数相关联，并且集合基于 HashMap 。但是，如果您引入足够多的字符来开始发生哈希冲突，则明显的顺序并不完全一致:

; the whole alphabet is small enough to avoid collisions
user=> (apply str (set "abcdefghijklmnopqrstuvwxyz"))
"abcdefghijklmnopqrstuvwxyz"
; and observe the hashes are indeed sequential
user=> (map hash (set "abcdefghijklmnopqrstuvwxyz"))
(97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122)

; but go from 26 to 36 elements, and you start to see collisions
user=> (apply str (set "0123456789abcdefghijklmnopqrstuvwxyz"))
"abcdefghijklmno0p1q2r3s4t5u6v7w8x9yz"
user=> (map hash (set "0123456789abcdefghijklmnopqrstuvwxyz"))
(97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 48 112 49 113 50 114 51 115 52 116 53 117 54 118 55 119 56 120 57 121 122)

但当然，如您所知，这不是一个定义的行为，而只是目前的实现方式。

现在，您会问为什么数字不会发生这种情况:原因是，Clojure 明确避免了这种情况! (.hashCode 1) 返回 1，因为 Java 就是这样定义其哈希码的。但 Clojure's hash function 使用 murmur3，它返回的数字值与仅返回输入的值完全不同:(hash 1) 生成 1392991556。我不是这方面的专家，但我相信使用 murmur 的主要动机出于安全原因，不是使用 Java 内置的哈希函数来避免哈希冲突。定时攻击什么的？