В чем разница между хэш-картой и массивом-картой в clojure?

Clojure имеет массив-карту и хэш-карту, я не мог понять разницу между ними. Может ли кто-нибудь объяснить, если это возможно, с примером того, когда любой из них будет использоваться?

Ответ 1

массивные карты сохраняют порядок вставки, но вы не должны полагаться на это поведение, за исключением очень простых случаев, когда вы знаете, что карта не будет изменена. Используйте упорядоченную коллекцию, если вам действительно нужно это поведение.

массивы-массивы должны использоваться для очень маленьких карт (сейчас 16 ключей), поскольку производительность поиска и "модификации" лучше, чем хэш-карта такого же размера:

(def arraymap (array-map :f 1 :g 2 :h 4 :y 5 :w 4))     
(def hashmap (hash-map :f 1 :g 2 :h 4 :y 5 :w 4))

(defn add-2-keys [m]
  (assoc m :new 2 :w 4))

(defn access-all-keys [m]
  (mapv m [:f :g :h :y :w :not-there]))

(use 'criterium.core)

; Modification 
(bench (add-2-keys array map))
Execution time mean : 125.640082 ns    
(bench (add-2-keys hashmap))
Execution time mean : 150.918197 ns

; Access
(bench (access-all-keys arraymap))
Execution time mean : 260.547035 ns
(bench (access-all-keys hashmap))
Execution time mean : 305.350156 ns

Ответ 2

Карты массивов и хэш-карты имеют один и тот же интерфейс, но карты массивов имеют сложность поиска O(N) (т.е. реализуются как простой массив записей), а хэш-карты имеют O(1) сложность поиска.

Массивные карты имеют преимущество (которое вам не нужно большую часть времени), что они поддерживают порядок вставки, поэтому, когда вы выполняете любую операцию, которая выполняет итерацию по карте (например, map или reduce), вы может обрабатывать записи в том же порядке, что и при их вставке.

Обратите внимание, что если вы "изменяете" (в смысле постоянной коллекции) карту массива повторно, в какой-то момент он станет хэш-картой. например.

user=> (type (apply assoc (array-map) (zipmap (range 10) (range 10))))
clojure.lang.PersistentArrayMap
user=> (type (apply assoc (array-map) (zipmap (range 100) (range 100))))
clojure.lang.PersistentHashMap

В принципе, всегда предпочитайте хэш-карты, если вам не нужен порядок клавиш. Кроме того, если вы используете карты массивов, имейте в виду компромисс производительности поиска.