HashMap
版本结构比较
jdk1.7时，hashmap为数组+链表
jdk1.8时，hashmap为数据+链表+红黑树，当链表长度大于8时（前提是table长度大于等于64，否则优先扩容）转化为红黑树，退化为红黑树有2个条件：
1.remove时退化
// 在 removeTreeNode的方法中// 在红黑树的root节点为空 或者root的右节点、root的左节点、root左节点的左节点为空时 说明树都比较小了if (root == null || (movable && (root.right == null || (rl = root.left) == null|| rl.left == null))) {tab[index] = first.untreeify(map); // too smallreturn;}
2.在扩容时 low、high 两个TreeNode 长度小于6时 会退化为链表。
Hash方法（1.8）
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
用三目表达式，key如果为空返回0，否则返回key.hashCode()前16位与后16位异或操作得到的值(为了使值更加散列)。
hash函数对key做了特殊处理，故key可以为null。
不用原始hashcode的原因
不用原始hashcode主要是因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为 -2147483648~2147483647，前后加起来大概 40 亿的映射空间，一个 40 亿长度的数组内存太大了放不下。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。故使用异或操作使hash值更加离散，降低hash碰撞。
put方法
jdk1.8使用的是尾插法，1.7的时候使用的是头插法（头插法更快，但高并发时容易产生循环链）
/*** Implements Map.put and related methods.** @param hash hash for key* @param key the key* @param value the value to put* @param onlyIfAbsent if true, don't change existing value* @param evict if false, the table is in creation mode.* @return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> 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<K,V>)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 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}
1.先判断table是否为空，空的话resize
2.先计算下标位置,即取模操作：(n - 1) & hash ，位运算速度>%mod。
n-1 ：如n为16位，那n-1是00001111，后面的全是1，与hash与操作，可以得到在容量内的坐标（后4位的值），类是取模。
若哈希槽上有空位，则直接插入哈希槽中
3.若哈希槽中没有位置，则先判断哈希槽上节点是否是TreeNode，是则新增一个TreeNode插入红黑树中
4.不是则是链表结构，在链表最后插入Node
5.判断插入节点后是否需要扩容。
hashmap在jdk1.8相对1.7中的优化
1.Java1.8 相比 1.7 做了调整，1.7 做了四次移位和四次异或，但明显 Java 8 觉得扰动做一次就够了，做 4 次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。
//1.7static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}//1.8static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
2.数组+链表改成了数组+链表或红黑树；
3.链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后；
4.扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，位置不变或索引+旧容量大小；
5.在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容。
扩容条件
threashold（扩容阈值） = capacity*loadFactor;当数组大小超过threashold时进行扩容。
1.loadFactor初始值为什么为0.75
rehash
jdk1.7时需要重新计算hash值，1.8不需要重新 hash 就可以直接定位原节点在新数据的位置，这是由于扩容是扩大为原数组大小的 2 倍，用于计算数组位置的掩码仅仅只是高位多了一个 1，举个例子：
扩容前长度为 16，用于计算 (n-1) & hash 的二进制 n - 1 为 0000 1111，
扩容后为 32 后的二进制就高位多了 1，============>为 0001 1111。
因为是 & 运算，1 和任何数 & 都是它本身，那就分二种情况，如下图：原数据 hashcode 高位第 4 位为 0 和高位为 1 的情况；
第四位高位为 0，重新 hash 数值不变，第四位为 1，重新 hash 数值比原来大 16（旧数组的容量）。
安全问题
jdk1.7时
死锁(Jdk1.7存在)以及get操作可能带来的数据丢失(数据被覆盖)。
Jdk7-扩容死链分析
死锁问题核心在于下面代码，多线程扩容导致形成的链表环!
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;//第一行
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//第二行
e.next = newTable[i];//第三行
newTable[i] = e;//第四行
e = next;//第五行
}
}
}
去掉了一些冗余的代码， 层次结构更加清晰了。
- 第一行：记录oldhash表中e.next
- 第二行：rehash计算出数组的位置(hash表中桶的位置)
- 第三行：e要插入链表的头部， 所以要先将e.next指向new hash表中的第一个元素
- 第四行：将e放入到new hash表的头部
- 第五行： 转移e到下一个节点， 继续循环下去
单线程扩容
假设：hash算法就是简单的key与length(数组长度)求余。hash表长度为2，如果不扩容， 那么元素key为3,5,7按照计算(key%table.length)的话都应该碰撞到table[1]上。
扩容：hash表长度会扩容为4重新hash，key=3 会落到table[3]上(3%4=3)， 当前e.next为key(7), 继续while循环重新hash，key=7 会落到table[3]上(7%4=3), 产生碰撞， 这里采用的是头插入法，所以key=7的Entry会排在key=3前面(这里可以具体看while语句中代码)当前e.next为key(5), 继续while循环重新hash，key=5 会落到table[1]上(5%4=3)， 当前e.next为null, 跳出while循环，resize结束。
如下图所示
多线程扩容
下面就是多线程同时put的情况了， 然后同时进入transfer方法中：假设这里有两个线程同时执行了put()操作，并进入了transfer()环节
while(null != e) {
Entry<K,V> next = e.next;//第一行，线程1执行到此被调度挂起
int i = indexFor(e.hash, newCapacity);//第二行
e.next = newTable[i];//第三行
newTable[i] = e;//第四行
e = next;//第五行
}
那么此时状态为：
从上面的图我们可以看到，因为线程1的 e 指向了 key(3)，而 next 指向了 key(7)，在线程2 rehash 后，就指向了线程2 rehash 后的链表。
然后线程1被唤醒了：
- 执行e.next = newTable[i]，于是 key(3)的 next 指向了线程1的新 Hash 表，因为新 Hash 表为空，所以e.next = null，
- 执行newTable[i] = e，所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了，e 处理完毕。
- 执行e = next，将 e 指向 next，所以新的 e 是 key(7)
然后该执行 key(3)的 next 节点 key(7)了:
- 现在的 e 节点是 key(7)，首先执行Entry next = e.next,那么 next 就是 key(3)了
- 执行e.next = newTable[i]，于是key(7) 的 next 就成了 key(3)
- 执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(7)
- 执行e = next，将 e 指向 next，所以新的 e 是 key(3)
此时状态为：
然后又该执行 key(7)的 next 节点 key(3)了：
- 现在的 e 节点是 key(3)，首先执行Entry next = e.next,那么 next 就是 null
- 执行e.next = newTable[i]，于是key(3) 的 next 就成了 key(7)
- 执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(3)
- 执行e = next，将 e 指向 next，所以新的 e 是 key(7)
jdk1.8时
jdk1.8扩容跳过了Jdk7扩容的坑，使用尾插法，采用高低位拆分转移方式(不需要rehash,速度快)，但并发场景下，扩容仍然会有数据覆盖问题。
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null; //低位指针
Node<K,V> hiHead = null, hiTail = null; //高位指针
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
HashMap与HashTable
Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。
为啥 Hashtable 是不允许 KEY 和 VALUE 为 null, 而 HashMap 则可以呢？
因为Hashtable在我们put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码
但是你还是没说为啥Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null？
如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理,另外提一下ConcurrentHashMap是fail-safe机制。
安全失败（fail—safe）大家也可以了解下，java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。复制原集合的一份数据出来，然后在复制的那份数据遍历
- 实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。Dictionary 是 JDK 1.0 添加的，貌似没人用过这个，我也没用过。
- 初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
- 扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。
- 迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。所以，当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。
快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。
集合在被遍历期间如果内容发生变化，就会改变modCount的值。
每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
Tip：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。
因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
其他
1.为什么在链表长度达到8的时候转为红黑树？
虽然当长度8的时候概率十分低，但为了防止有人恶意重写或者不好的hashcode()方法导致链很长，综合空间复杂度和时间复杂度，将值设为8；
选择n>=8时转化为红黑树(当hash槽大于64时)，小于6时退化为普通Node。
链表长度小的时候，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
2.jdk1.7的时候hashMap，transfor()时存在死链问题，1.8的时候存在值覆盖的问题。
3.初始化，默认是16，若new HashMap<>(n),则初始容量为>=n的且为2的指数次幂，即为2^m.
为什么一定要转成2的指数次幂？
使用2的指数次幂是因为取模操作是n-1&hash,n-1表示的数二禁止表示后面的位数必须全为1,为n-1=15时为0000 1111。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
若有收获，就点个赞吧
0 人点赞
