关于hashmap:关于HashMap这篇文章已经总结很详细了

24次阅读

共计 2828 个字符,预计需要花费 8 分钟才能阅读完成。

HashMap 的底层数据结构?

HashMap 是咱们十分罕用的数据结构,由 数组和链表组合形成 的数据结构。数组里每个中央都存了 Key-Value 这样的实例,在 Java7 叫 Entry,在 Java8 中叫 Node。

初始化后所有的地位都为 null,在 put 插入的时候会依据 key 的 hash 去计算一个 index 值。

链表?为啥须要链表?链表具体是什么样的?

数组的长度是无限的,在无限的长度外面应用哈希,哈希本事就存在肯定的概率性,当两个 key 的 hash 一样时就会 hash 到一个值上,造成链表。

每个节点都会有本身的 hash、key、value、以及下个节点,Node 的源码:

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

链表,新的 Entry 节点在插入链表的时候,是怎么插入的?

Java8 之前是头插法,就是说新来的值会取代原有的值,原有的值就顺推到链表中去,因为过后设计这段代码的作者认为起初的值被查找的可能性更大一点,晋升查找的效率。

Java8 之后,都是采纳尾部插入。

为什么改用尾插法?

改用尾插法是因为 HashMap 的扩容机制,数组容量是无限的,数据屡次插入,到肯定的数量就会进行扩容,也就是 resize。

什么时候 resize?

resize 的两个条件:

  • Capacity:HashMap 以后长度。
  • LoadFactor:负载因子,默认值 0.75f
/**
 * The load factor used when none specfified in constructor
 */
static final float FEFAULT_LOAD_FACTOR=0.75f;

简略的了解就是,如果以后容量是 100,当存进第 76 个的时候,判断发现须要进行 resize 了,那就进行扩容。

HashMap 是怎么扩容的?

分两步:

  • 扩容:创立一个新的 Entry 空数组,长度为原数组的 2 倍。
  • Rehash:遍历原 Entry 数组,把所有的 Entry 从新 Hash 到新数组。

为什么不间接复制,为什么须要从新 Hash?

因为长度扩充后,Hash 的规定也随之扭转。

Hash 公式:index = HashCode(Key)  & (Length-1)

扩容后 Length 产生了扭转,从新计算的 index 与扩容前显著不一样。

Java8 以前用头插法,Java8 之后为什么改为尾插法了呢?

先举个例子吧,咱们当初往一个容量大小为 2 的 put 两个值,负载因子是 0.75,咱们在 put 第二个的时候就会进行 resize,当初咱们要在容量为 2 的容器外面用不同线程插入 A,B,C,如果咱们在 resize 之前打个断点,那意味着数据都插入了然而还没进行 resize 那扩容前可能是这样的,咱们能够看到链表的指向 A ->B->C

Tip:A 的下一个指针是指向 B 的

因为 resize 的赋值形式,也就是应用了单链表的头插入方式,同一地位上新元素总会被放在链表的头部地位,在旧数组中同一条 Entry 链上的元素,通过从新计算索引地位后,有可能放到了新数组的不同地位上。

可能呈现如下状况,B 的下个指针指向了 A:

一旦几个线程同时都调整实现,就可能呈现环形链表。

如果这个时候去取值,就会呈现 –Infinite Loop。

Java8 之后的尾插法

应用头插法会扭转链表的程序,如果应用尾插,在扩容的时候放弃链表元素原来的程序,就不会呈现链表成环的问题了。

就是说本来是 A ->B,在扩容后那个链表还是 A ->B


Java7 在多线程操作 HashMap 时可能引起死循环,起因是扩容转移后前后链表程序倒置,在转移过程中批改了原来链表中节点的援用关系。Java8 在同样的前提下并不会引起死循环,起因是扩容转移后前后链表程序不变,放弃之前节点的援用关系。

那是不是意味着 Java8 就能够把 HashMap 用在多线程中?

Java8 中 HashMap 即便不会呈现死循环,然而通过源码看到 put/get 办法都没有加同步锁,多线程状况下最容易呈现的就是:无奈保障上一秒 put 的值下一秒 get 的时候还是原值,所以线程平安还是无奈保障。

HashMap 的默认初始化长度是多少?

源码显示初始化大小是 16

/**
 * The default initial capacity -MUST be a power of two .
 */
static final int DEFAULT_INITIAL_CAPACITY = 1<<4;  //aka 16

这样是为了位运算的不便,位与运算比算数计算的效率高了很多,之所以抉择 16,是为了服务将 Key 映射到 index 的算法。咱们是通过 key 的 HashCode 值去做位运算,

比方说:key 为“你好”的二进制是 123456 那二进制就是 11110001001000000

index 的计算公式;index = hashCode(key) & (Length-1)

15 的二进制是 1111,那 11110001001000000 & 1111 十进制就是 4

用位与运算成果和取模一样,性能也进步了不少!

为什么用 16 不必别的呢?

因为应用 2 的幂的数字的时候,Length- 1 的值所有二进制位全为 1,这种状况下,index 的后果等同于 HashCode 后几位的值。只有输出的 HashCode 自身散布平均,Hash 算法的后果就是均匀分布的。

这是为了实现均匀分布。

为啥我没重写 equals 办法的时候须要重写 HashCode 办法呢?用 HashMap 举例

因为在 Java 中,所有的对象都继承于 Object 类。Object 类中有两个办法,equals、hashCode,这两个办法都是用来比拟两个对象是否相等的。在未重写 equals 办法时候咱们是继承 object 的 equals 办法,那个 equals 是比拟两个对象的内存地址,显然咱们 new 了两个对象内存地址必定不一样,在 HashMap 中通过 key 的 hashCode 去寻找 index 的,如果 index 一样就造成了链表了,当咱们依据 key 去 hash 而后计算出 index,找到了 2 两个或多个,具体找哪个值就不晓得了

equals!所以咱们对 equals 办法进行了重写,倡议肯定要对 hashCode 办法重写,以保障雷同的对象返回雷同的 hash 值,不同的对象返回不同的 hash 值。

HashMap 的线程是不平安的,怎么解决 HashMap 在线程平安的场景

在须要线程平安的场景应用个别应用 HashTable 或者 ConcurrentHashMap,然而 HashTable 的并发度的起因基本上很少应用,存在线程不平安的场景的时候咱们都是应用 ConcurrentHashMap。

HashTable 的源码很简略粗犷,间接在办法上加锁,并发度很低,最多同时容许一个线程拜访,ConcurrentHashMap 就好很多,1.7 和 1.8 有较大的不同,不过并发度都比前者好太多了。

学习技术,问题探讨,举荐退出我的 Java 学习园地。

正文完
 0