jdk7 中HashMap的知识点总结

jdk7 中HashMap的知识点总结

HashMap中的几个重要变量

默认初始容量,必须是2的n次方

static final int DEFAULT_INITIAL_CAPACITY = 16;

最大容量，当通过构造方法传入的容量比它还大时，就用这个最大容量，必须是2的n次方

static final int MAXIMUM_CAPACITY = 1 << 30;

默认负载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

用来存储键值对，可以看到键值对都是存储在Entry中的

transient Entry[] table;

//capacity * load factor,超过这个数就会进行再哈希

int threshold;

HashMap中的元素是用名为table的Entry数组来保存的，默认大小是16

capacity:数组的容量

load_factor:负载因子

threshold：实际能承载的容量，等于上面两个相乘，当size大于threshold时，就会进行rehash

jdk7中在面对key为String的时候采用了区别对待，会有alternative hashing，但是这个在jdk8中已经被删除了

存储结构

Entry是一个链表结构，不仅包含key和value，还有可以指向下一个的next

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;

}

...

put方法

public V put(K key, V value) {

if (key == null)

return putForNullKey(value);

int hash = hash(key);

int i = indexFor(hash, table.length);

for (Entry e = table[i]; e != null; e = e.next) {

Object k;

if (e.hash http://== hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

modCount++;

addEntry(hash, key, value, i);

return null;

}

首先通过hash方法对hashcode进行处理：

final int hash(Object k) {

int h = 0;

h ^= k.hashCode();

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

可以看到只是在key的hashcode值上做了一些处理，通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标：

static int indexFor(int h, int length) {

return h & (length-1);

}

这个方法其实相当于对table.length取模。

当需要插入的key为null时，调用putForNullKey方法处理：

private V putForNullKey(V value) {

for (Entry e = table[0]; e != null; e = e.next) {

if (e.key == null) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

modCount++;

addEntry(0, null, value, 0);

return null;

}

putForNullKey方法只从table[0]这个位置开始遍历，因为key为null只放在table中的第一个位置，下标为0，在遍历中如果发现已经有key为null了，则替换新value，返回旧value，结束；如果还没有key为null，调用addEntry方法增加一个Entry:

void addEntry(int hash, K key, V value, int bucketIndex) {

if ((size >= threshold) && (null != table[bucketIndex])) {

resize(2 * table.length);

hash = (null != key) ? hash(key) : 0;

bucketIndex = indexFor(hash, table.length);

}

createEntry(hash, key, value, bucketIndex);

}

可以看到jdk7中resize的条件已经发生改变了，只有当 size>=threshold并且 table中的那个槽中已经有Entry时，才会发生resize。即有可能虽然size>=threshold，但是必须等到每个槽都至少有一个Entry时，才会扩容。还有注意每次resize都会扩大一倍容量

void createEntry(int hash, K key, V value, int bucketIndex) {

Entry e = table[bucketIndecNyftzx];

table[bucketIndex] = new Entry<>(hash, key, value, e);

size++;

}

最后看createEntry，它先保存这个桶中的第一个Entry，创建新的Entry放入第一个位置，将原来的Entry接在后面。这里采用的是头插法插入元素。

get方法

其实get方法和put方法如出一辙，怎么放的怎么拿

public V get(Object key) {

if (key == null)

return getForNullKey();

Entry entry = getEntry(key);

return null == entry ? null : entry.getValue();

}

key为null时，还是去table[0]去取：

private V getForNullKey() {

for (Entry e = table[0]; e != null; e = e.next) {

if (e.key == null)

return e.value;

}

return null;

}

否则调用getEntry方法：

final Entry getEntry(Object key) {

int hash = (key == null) ? 0 : hash(key);

for (Entry e = table[indexFor(hash, table.length)];

e != null;

e = e.next) {

Object k;

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

return e;

}

return null;

}

这个方法也是通过key的hashcode计算出它应该所在的下标，再遍历这个下标的Entry链，如果key的内存地址相等（即同一个引用）或者equals相等，则说明找到了

hash的原则

A、等幂性。不管执行多少次获取Hash值的操作，只要对象不变，那么Hash值是固定的。如果第一次取跟第N次取不cNyftz一样，那就用起来很麻烦.

B、对等性。若两个对象equal方法返回为true，则其hash值也应该是一样的。举例说明：若你将objA作为key存入HashMap中，然后new了一个objB。在你看来objB和objA是一个东西（因为他们equal），但是使用objB到hashMap中却取不出来东西。

C、互异性。若两个对象equal方法返回为false，hash值有可能相同，但最好是不同的，这个不是必须的，只是这样做会提高hash类操作的性能（碰撞几率低）。

解决hash碰撞的方法：

开放地址法

链地址法

hashmap采用的就是链地址法，这种方法好处是无堆积现象，但是next指针会占用额外空间

和jdk8中的HashMap区别

在jdk8中，仍然会根据key.hashCode()计算出hash值，再通过这个hash值去定位这个key，但是不同的是，当发生冲突时，会采用链表和红黑树两种方法去处理，当结点个数较少时用链表（用Node存储），个数较多时用红黑树（用TreeNode存储），同时结点也不叫Entry了，而是分成了Node和TreeNode。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。jdk8中的HashMap中定义了一个变量TREEIFY_THRESHOLD，当节点个数>= TREEIFY_THRESHOLD - 1时，HashMap将采用红黑树存储

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。