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

Question

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

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

Answer 1

它基本上看起来像这样:

 this is the main array
   ?
[Entry] ? Entry ? Entry      ? here is the linked-list
[Entry]
[Entry] ? Entry
[Entry]
[null ]
[null ]

所以你有一个主数组,其中每个索引对应一些哈希值(mod'ed*到数组的大小).

然后它们中的每一个将指向具有相同散列值的下一个条目(再次为mod'ed*).这是链接列表的来源.

*:作为技术说明,它在被mod编辑之前首先使用不同的函数进行哈希处理,但是,作为基本实现,只需进行修改即可.

Answer 2

散列映射的条目存储在"桶"中:每个散列映射都有一个阵列,并且该阵列根据键哈希码将条目放置在一个位置(例如position = hashcode%arraysize).

如果多个条目在同一个桶中结束,那么这些条目将存储在链表中(另请参阅Dukelings的答案).因此,bucket-metaphor:每个数组条目都是一个"存储桶",您只需转储所有匹配的键.

由于您需要访问此列表中的随机位置,因此您必须为存储桶使用数组以获得干扰的"恒定时间"行为.在存储桶中,您必须遍历所有元素,直到找到所需的键,因此您可以使用链接列表,因为它更容易追加(不需要调整大小).

这也显示了对一个好的散列函数的需求,因为如果所有键只散列到几个值,你将获得搜索的长链表和许多(快速访问)空桶.

Answer 3

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

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

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

你自己看 ：

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> 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<K,V> m) {
        }

        /**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }