java进阶(29)–HashMap集合

一、HashMap简介

1、HashMap底层是哈希表结构,类似字典,初始化如下:

 

2、哈希表结构:

是一个数组+单向链表的结构体

数组:查询效率较高,随机增删效率很低

单向链表:在随机增删方面效率较高,查询方面效率很低

哈希表将以上两种数据结构融合在一起,充分发挥它们各自的优点。

 

3、HashMap集合底层是数组,Node<k,v>[]tables;

hash为哈希值,是HashCode方法执行的结果,通过哈希算法可以转换为数组的下标;

key,value为Map的key与value,next为下一个内存地址

 

4、map.put(k,v)的实现原理

k,v封装到Node对象内,底层调用hashCode()方法得出hash值,通过哈希算法/哈希函数,将hash值转换成数组下标。

如果下标对应的位置上面没有元素,Node添加到位置上;

如果下标对应的位置上有链表,拿k与链表每个节点k进行equals,如所有equals方法都false,新节点将添加到尾部;

如果有一个euals返回true,那么这个节点的value值将会覆盖

 

5、map.get(k)的实现原理

调用k的hashCode()方法得出哈希值,通过哈希算法转换成数组下标,通过数组下标快速定位到某个位置,位置上什么都没有话,返回null;

如果这个位置上有单向链表,那么会拿着参数k和单向链表上每个节点的k进行equals,如果所有的equals返回false,囊二get方法返回null。

主要其中某一个节点的k和参数k equals返回true,那么此时这个节点的value就是我们要找的value,既为get方法的最终返回value

 

6、HashMap的key部分元素需要重写equals方法hashCode方法。也就是hashSet集合中的元素需要重写equals方法hashCode方法。

 

7、HashMap使用不当时会发生性能问题:

假设所有的hashCode方法返回值都相等,那么底层会变成单向链表,即散列分布不均匀。

什么是散列分布均匀:100个元素,10个单向链表,每个单向链表中包含10个节点。

假设所有的hashCode方法返回均不一样,那么底层会变成数组,即散列分布不均匀。

散列分布均匀需要重写hashCode方法有一定的技巧

 

8、HashMap集合底层数组达到75%容量时,数组是开始扩容,默认数组容量为16,初始化容量必须是2的倍数,为达到散列分布均匀,且可以提高hashMap集合存取效率。

 

9、HashMap元素存取什么时候不需要执行equals方法:k.hashCode方法返回的哈希值的数组下标位置为null的时候,equals不再需要执行。

 

10、HashMap JDK8改进:

如果哈希表的单向链表中元素>8,单向链表会变成红黑树,当红黑树上节点数量<6,会重新把红黑数变成单向链表

 

11、哈希表数据结构注意事项:

如果o1与o2的hash值相同,一定在同一个单向链表上,

如果o1与o2的hash值不同,但由于哈希算法执行结束后转换的数组下标可能相同,此时会发生“哈希碰撞”

 

二、实例说明:

1、测试HashMap元素特点:key为integer,它的hashCode与equals均已经被重写

 

2、遍历Map集合-元素将被无须取出

 

3、重写quals与hashCode方法

未重写hashCode与equals

 重写hashCode与equals后

 4、HashMap的key与value可以为空吗,

HashMap可以,Hashtable则不行