HashMap

发表于 | 阅读次数 | 阅读数

HashMap

#####存储结构

主要是数组+链表+红黑树（后来增加）
`

int threshold;             // 所能容纳的key-value对极限 length（默认12）* loadFactor

final float loadFactor;    // 负载因子默认0.75f

int modCount;  

int size;            //实际存储的kv对数

table数组：存储node数组 主要的属性如下：

public static class Node<K,V> implements Map.Entry<K,V> {

    final int hash;//定位在数组中的位置
    final K key;
    V value;
    Node<K,V> next;//链表的下一个node
}

`

#####问题

  1. 为什么初始值是16？HashTable为什么是11？回答：在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数。Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
  2. 拉链过长咋办？回答：对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。
  1. 1.6的扩容是 size++ >= threshold 插入后11时就扩大

    1.8的扩容是 ++size > threshold 插入后12时 扩容

#####主要的方法
1.hash的过程是确定在数组中的位置。散列的越好就越均匀。

过程：
方法一：
`

static final int hash(Object key) {   

//jdk1.8 & jdk1.7 
int h;
 // h = key.hashCode() 为第一步 取hashCode值
 // h ^ (h >>> 16)  为第二步 高位参与运算
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

方法二：
`

static int indexFor(int h, int length) {  
//jdk1.7的源码，jdk1.8没有这个方    法，但是实现原理一样的
 return h & (length-1);  //第三步 取模运算
}

`
步骤：1->取hashcode 2->高位运算 3->取模运算

2.put方法
执行流程
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

0%