如何在java中使用linkedlist或array在内部实现hashmap

hashmap内部如何实现？ 我在某处读到它使用链表，而在某些地方它被称为数组。

我尝试研究hashset的代码并找到了入口数组，然后使用了linkedlist

Answer 1

它基本上看起来像这样：

  this is the main array ↓ [Entry] → Entry → Entry ← here is the linked-list [Entry] [Entry] → Entry [Entry] [null ] [null ] 

所以你有一个主数组，其中每个索引对应一些哈希值（ mod *到数组的大小）。

然后它们中的每一个将指向具有相同散列值的下一个条目（再次mod *）。 这是链接列表的来源。

*：作为一个技术说明， 它在修改之前首先使用不同的函数进行哈希处理 ，但是，作为基本实现，只需修改即可。

Answer 2

散列映射的条目存储在“桶”中：每个散列映射都有一个arrays，并且该arrays根据键哈希码将条目放置在一个位置（例如，position = hashcode％arraysize）。

如果多个条目在同一个存储桶中结束，那么这些条目将存储在链接列表中（另请参阅Dukelings的答案）。 因此，bucket-metaphor：每个数组条目都是一个“存储桶”，您可以在其中转储所有匹配的键。

由于您需要访问此列表中的随机位置，因此您必须为存储桶使用数组以获得干扰的“恒定时间”行为。 在存储桶中，您必须遍历所有元素，直到找到所需的键，因此您可以使用链接列表，因为它更容易追加（不需要resize）。

这也显示了对一个好的哈希函数的需求，因为如果所有键只哈希到几个值，你将获得搜索的长链表和许多（快速访问）空桶。

Answer 3

HashMap有一个HashMap.Entry对象数组：

 /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table; 

我们可以说Entry是一个单向链表（例如HashMap.Entry链接称为“Bucket”），但实际上它不是java.util.LinkedList。

你自己看 ：

 static class Entry implements Map.Entry { final K key; V value; Entry next; int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap m) { } } 

Answer 4

HashMap内部使用Entry来存储键值对。 条目是LinkedList类型。

条目包含以下 – >

K键，

V值和

输入下一个>即桶位置的下一个条目。

 static class Entry { K key; V value; Entry next; public Entry(K key, V value, Entry next){ this.key = key; this.value = value; this.next = next; } } 

HashMap图 –

来自： http ： //www.javamadesoeasy.com/2015/02/hashmap-custom-implementation.html