HashMap

 

HashMap

HashMap无序,非同步,key允许为null,底层由数组+链表实现

HashMap的一个实例有两个影响其性能的参数: 初始容量和负载因子 。 容量是哈希表中的桶数,初始容量只是创建哈希表时的容量。 负载因子是在容量自动增加之前允许哈希表得到满足的度量。 当在散列表中的条目的数量超过了负载因数和电流容量的乘积,哈希表被重新散列 (即,内部数据结构被重建),使得哈希表具有桶的大约两倍。

//初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量 2的31次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//装载因子 0.75 设置过高虽然会减少空间,但会增加遍历的开销
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//桶的树化阈值:即 链表转成红黑树的阈值,在存储数据时,当链表长度 > 该值时,则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;

//桶的链表还原阈值:即 红黑树转为链表的阈值,当在扩容(resize())时(此时HashMap的数据存储位置会重新计算),在重新计算存储位置后,当原有的红黑树内数量 < 6时,则将 红黑树转换成链表
static final int UNTREEIFY_THRESHOLD = 6;

//最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表,否则,若桶内元素太多时,则直接扩容,而不是树形化,为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

HashMap常用方法

HashMap

JDK1.8中,对HashMap的hash算法和寻址算法的优化

hash算法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

h = key.hashCode()表示h是key对象的hashCode的hash值;h »> 16是h右移16位;最后将两个值进行异或运算,返回int值。

右移16位:int是4字节32位,右移16位后变成:左边16个0+右边原hash值的高16位

异或:二进制位运算。如果一样返回 0,不一样则返回 1。

hash算法的优化:对每个hash值,在它的低16位中,让高低16位进行异或,让它的低16位同时保持了高低16位的特征,尽量避免一些hash值后续出现冲突,大家可能会进入数组的同一位置。

寻址算法

(p = tab[i = (n - 1) & hash]) == null

tab 就是 HashMap 里的 table 数组 Node<K,V>[] table ;

n 是这个数组的长度 length;

hash 就是上面 hash() 方法返回的值;

寻址算法的优化:用与运算替代取模,提升性能。(由于计算机对比取模,与运算会更快)