HashMap底层分析

来源:互联网 时间:1970-01-01

1、HashMap的数据结构
HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。首先,HashMap类的属性中定义了Entry类型的数组。Entry类实现java.ultil.Map.Entry接口,同时每一对key和value是作为Entry类的属性被包装在Entry的类中。

Java代码 /*** The table, resized as necessary. Length MUST Always be a power of two.*/ transient Entry[] table; static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; …… } 

从底层分析,HashMap存储采用的是一个Entry类型的数组。而这个数组每个元素又是一个链表。在链表中前一个元素指向后一个元素。

2、HashMap的添加元素
根据key的重新计算元素的hashCode,根据hashCode得到这个元素在table数组中的位置(即下标),假如数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加进的放在链头,最先加进的放在链尾。假如数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。
public V put(K key, V value) { // HashMap答应存放null键和null值。 // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。 if (key == null) return putForNullKey(value); // 根据key的keyCode重新计算hash值。 int hash = hash(key.hashCode()); // 搜索指定hash值在对应table中的索引。 int i = indexFor(hash, table.length); // 假如 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 假如发现 i 索引处的链表的某个Entry的hash和新Entry的hash相等且两者的key相同,则新Entry覆盖旧Entry,返回。 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 假如i索引处的Entry为null,表明此处还没有Entry。 modCount++; // 将key、value添加到i索引处,也就是最开始,并让他的next指向原来第一个元素。 addEntry(hash, key, value, i); return null; 

3、HashMap读取数据
计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //找到hash对应的table位置,然后遍历找到key值相同的,返回value。 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } 
大小: 20.5 KB



相关阅读:
Top