欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashMap相关知识

程序员文章站 2022-06-04 19:26:06
...

数据结构及扩容原理

JDK8开始,结构变为数组+链表/红黑树,当单项链表元素超过8个,结构变为红黑树,红黑树上节点小于6个时,结构重新变为单项链表。
HashMap是无序的,加入顺序和取出顺序也不一样,初始化容量16,负载因子0.75,当容量达到75%时开始扩容,扩容2倍。原数组中的数据必须重新计算其在新数组中的位置,并放进去,所以效率低。引发思考,如果我们提前知道HashMap中要Put元素的数量,可以创建的时候申请足够容量。

数组

优点:存储区间连续,随机存储效率高,查找速度快O(1)。
缺点:由于存储空间连续所以暂用空间严重,插入、删除效率低,以为插入数据,该位置后的数据要往后移。

链表

优点:内存利用率高,插入、删除效率高。
缺点:不能随机查找,每次都是从第一个开始遍历。

put(k,v)原理

  1. 首先将k,v封装到Node对象中;
  2. 调用k的hashCode()方法,得出hash值;
  3. 通过哈希算法将hash值转换为数组下标;
  4. 若下标位置没有元素,将Node添加到该位置,若有链表,就会通过k和链表上每个节点的的k进行equals,如果所有equals都返回false,那么将Node加到链表末尾,如其中某个equals返回true,那么该节点被覆盖。

get(k)原理

  1. 先调用k的hashCode()方法得出哈希值,并通过哈希算法转换为数组下标;
  2. 如果数组位置什么都没有,则返回null,如果该位置有单项链表,那么会将k和单机链表上每一个节点进行equals;
  3. 如果所有equals都返回false,则get方法返回null,如果其中一个节点的k和参数k进行equals后返回true,则该节点的v就是要找的v

hashCode()和equals()

对HashMap的这两个方法需要重写,因为Object默认的这两个方法是如下的:
hashCode():是JDK根据对象的地址或字符串或数字算出来的int数值,叫哈希码。两个相等的对象有同样的哈希码。
equals():默认实现中,比较内存地址值。在String、Interger、Date中都被重写了,变成比较对象的成员变量值是否相同。重写该方法时通常也要重写hashCode(),因为要维护相等对象间拥有相同的哈希码。
“==”:在不重写equals()时,==和equals一样。重写后取决于你是怎么重写的。一般的重写步骤:

  1. 使用“==”检查参数是否为这个对象的引用
  2. 使用instanceof 检查参数是否为正确的类型
  3. 把参数转化为正确的类型
  4. 检查类中的每个关键域

举个栗子,String类中的==和equals,==比较两者地址是否相同,equals比较值是否相同。

        String str1 = "1";
        String str2 = "1";
        System.out.println(str1.equals(str2));
        System.out.println(str1 == str2);
        String str3 = new String("2");
        String str4 = new String("2");
        System.out.println(str3.equals(str4));
        System.out.println(str3 == str4);

所以这个结果是什么呢?
true true true false

线程安全性

为啥HashMap线程不安全呢?
JDK1.7中扩容时造成环形链和数据丢失,JDK1.8已解决,
JDK1.8中,还有数据覆盖的情况。
详见链接3.

线程安全的结构:HashtableConcurrentHashMap
两者都是线程安全的,比较如下,可查看链接4
HashTable:对所有容器状态访问都串行化了,通过synchronized关键字实现,严重降低了并发性,当多个线程竞争容器时,吞吐量严重降低。
ConcurrentHashMap:加锁颗粒度更细,最高允许16个线程同时访问,效率高。JDK1.8后,用 Node 数组+链表+红黑树的数据结构,并发控制使用 synchronized 和 CAS 来操作。

引用

感谢前辈们
[1]: http://baijiahao.baidu.com/s?id=1665667572592680093&wfr=spider&for=pc
[2]: https://blog.csdn.net/hfut_why/article/details/82915167
[3]: https://blog.csdn.net/swpu_ocean/article/details/88917958
[4]: https://www.jianshu.com/p/82e8d173f6e1

相关标签: Java基础