| HashMap的数据结构 | 您所在的位置：网站首页 › js中map数据结构红黑树 › HashMap的数据结构 |
HashMap的数据结构
|
在JDK1.7中HashMap基本数据结构是：Node[]数组+单向链表 在JDK1.8中HashMap基本的数据结构是：Node[]数组+单向链表+红黑树 关键参数：table——保存KV键值对的数组
每一个Node对象都要有一个hash,用这个hash计算这个对象在数组的什么位置 但是可能会存在两个Node对象hash值相同的情况，在这种情况下两个Node对象要存到一个位置上，这时就会形成一个链表（在相同的位置上如果要存放若干个Node,Node和Node之间就会形成一个链表）；从上图 Node next; 我们可以看出，这个链表是一个单向链表；但是链表的查找不便利，当如果链表里面的元素结点数量过多的时候，它会变成一棵树（红黑树），变成一颗使查询效率提高的有序的树（有序的树就可以通过二分查找的方式提高查询效率） HashMap的扩容方式：
HashMap用resize()进行扩容，那什么时候进行第一次扩容呢？就是当我们往里面去添加第一个元素的时候 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
我们一开使给它分配的默认长度是DEFAULT_INITIAL_CAPACITY常量:
如图所示：DEFAULT_INITIAL_CAPACITY的值为16；则我们一开始给它分配的长度就是16 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);通过数组长度和你当前key的hash值计算一个下标位置，然后把这个下标位置p拿出来，判断是否等于null;如果等于null则证明这个下标位置从来没有放过值，那就把我们当前的键值对放到这个位置；那么要怎么放呢？我们将i作为下标位置然后用newNode()将它放进去 else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } }如果p不等于null，则证明当前位置已经有值了 ，就产生了hash冲突；要解决hash冲突我们可以采用链地址法来存储；在1.7中采用的是头插法，容易产生宕机现象；在1.8中采用了尾插法 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;如果当时这个结点的hash值和我们算出来的hash值相同；并且我当前的key和你的key一样，或者我当前key的内容和你一样；那就证明这两个值就是一样的，那就做一个覆盖操作 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);如果两个值不一样，且这个值它不是一个链表而是一个树的时候，我们就要把这个值放到这个树里面 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; }如果两个值不相等并且不是一个树的时候，当(e = p.next) == null就证明我找到这个链表的尾结点了；那么我们就把当前的值形成一个新的结点放到这个尾结点的后面；但是如果链表过长，查找的时间复杂度就过大了，这时候我们就可以用树来，减少查找的时间复杂度 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);
binCount为当前链表中结点的个数，如果binCount大于等于8了，就要创建一个树了
但是在创建一个树之前，我们要先判断数组的长度是否小于64，如果小于64，这时我们不把这个链表直接变成树，我们会先用resize（）先进行扩容；数组长度就会越来越大；当链表长度超过8了，并且数组长度比64大了，那我们就不用再进行扩容了；这时我们就会把每一个结点的这个值拿出来，一个一个的变成树给它放进去（就是把链表的结点，变成树的结点） loadFactor:float——加载因子（填充因子） 扩容时的初始化（添加第一个K，V时）： 无参构造方法：public HashMap() 数组默认容量为16，加载因子为0.75（即这个数组的容量用到75%就要进行扩容了，不能等到数组完全用完） 有参构造方法：public HashMap(int initialCapacity,float loadFactor) 自己指定容量（但容量值一定是2的n次幂） 扩容方法：1.加入元素时，如果链表长度大于阈值（默认为8）并且数组长度小于64，会产生数组扩容 2.添加元素后，当HashMap中的元素个数超过【数组大小x加载因子（loadFactor）】时，原数组扩容两倍
|
【本文地址】