1.特点
- 线程不安全
为什么不安全：【主要是没有对其上锁】 - 见注解 fast-fall机制
- 扩容操作resize 当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失
- hash碰撞的时候，多个线程参与的时候有时候会有某个线程的操作覆盖掉其他线程操作的结果
如何线程安全的使用:
1.直接换掉 使用Hashtable 这个里面主要的是会对方法加上synchronized，其他线程就会去竞争这个锁，其余的继续等待。
- ConcurrentHashMap 【优】//TODO学习点
- SynchronizedMap
- 无序
- key值不允许重复
2.基础结构
HashMap 的基本结构是基于
数组(table[i])+链表/红黑树(Node<K,V>) 结构 如下图
hashmap基本数据结构
【数组，在这里被称为位桶(bucket)，每个table[i] 里的 i 被称作bucketIndex（bucketIndex这个是根据hash 计算得到的））】
那么图中的链表结构是怎么去实现的呢？重点就是我们的这个Node了。
链表结构
【链表结构：单链表，新的节点放置在该table[i]里原节点next属性为null的节点里】
以前是使用的数组+链表的方式，在数组中查找的时间复杂度为O(1),然而在链表里就需要一个个去循环这里的时间复杂度就是O(n)，万一恶意插入到某个桶里，不断的插入，这样循环查询时间就比较可怕了。然而在1.8的时候就发生了改变，当某个桶的节点到达一定的数值的时候就会转换为红黑树。
文中有关红黑树的方法 不进行深入学习，打算之后认真在去学习下，打算后期再写个有关红黑树的学习记录。
存入操作过程
put 新增加了3个参数，然后直接调用了putVal方法
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
//put操作直接跳到 putVal
public V put(K key, V value) {
//通过key获取了这个hash值 当key==null 返回0 否则则计算hashcode
//默认如果存在key相等且hashcode相等就直接替换
return putVal(hash(key), key, value, false, true);
}
So,重点的来了，就是我们主要进行插入动作的主要方法：
/**
* 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 - false表示这个表示如果找到已经存在的值，默认更新
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none //返回值 如果是新插入的节点返回的就是Null 否则返回被替换的原来的值
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;//table 就是那个位桶
Node<K,V> p; //hash指向的桶的第一个节点 Node<K,V> 注解3
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//初始化的分配空间（第一个元素会走进来）
n = (tab = resize()).length;//调用resize方法调整大小后的table.初始化都为16；
if ((p = tab[i = (n - 1) & hash]) == null)//bucketIndex所在指向数组tab的位置(第i个桶)为null，直接put
tab[i] = newNode(hash, key, value, null);
else {//bucketIndex所在指向数组tab的位置(第i个桶)有元素 那么需要遍历这个节点 这里就是发生碰撞（注解1)
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果和桶里第一个节点kay,hash均相等
e = p;//直接更新这个元素 p表示该桶里面第一个节点
else if (p instanceof TreeNode) //如果这个是红黑树的插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//红黑树的插入 注解 4
else {//链表的插入
for (int binCount = 0; ; ++binCount) {//循环里去寻找这个链表
if ((e = p.next) == null) {//如果找到末尾了都没有找到key相同的节点 注意这里e设置为为Null
p.next = newNode(hash, key, value, null);//插入新节点
if (binCount >= TREEIFY_THRESHOLD - 1)//binCount>=7则链表转树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) // 找到了hash、key均相等，说明此时的节点==待插入节点，跳出去。跳出去就是更新了，跳出去的时候如果。这里出去的时候e一定不为null
break;
p = e;
}
}
//根据e来判断，当链表或者红黑树里面存在了这个key的值
if (e != null) { // existing mapping for key
V oldValue = e.value;//旧的值
if (!onlyIfAbsent || oldValue == null)// 参数主要决定当该键已经存在时，是否执行替换 默认替换@param onlyIfAbsent if true, don't change existing value
e.value = value;
afterNodeAccess(e);//TODO调用linkedHashMap,move node to last
return oldValue;//返回的是旧的值
}
}
++modCount;//结构改变次数，fast-fail机制(注解2)
if (++size > threshold)//检测是否到了阀值
resize();//达到了就需要重新调整大小 注解5 resize() 方法
afterNodeInsertion(evict);
return null;
}
注解1：碰撞
调用put 方法的时候会调用k.hashcode 获取hash码，然后找到一个存放位置，被称为bucketIndex。如果hashCode不同，equals一定为false，如果hashCode相同，equals不一定为true。当hashCode相同的时候可能发生碰撞，当碰撞发生时，计算出的bucketIndex也是相同的，这时会取到bucketIndex位置已存储的元素，通过equals来比较，
(onlyIfAbsent入参为false)当相等的时候，就会替换原来的value;如果不一样，那么便查找该链表/红黑树里其他节点是否有相等的，没有再作为一个新的节点挂在该桶下方。
注解2：fast-fail机制
“快速失败”也就是fail-fast，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。因为hashmap不是线程安全的，在这里当某个线程进入put操作的时候 会修改modCount ，另一个线程如果正在遍历这个map，那么他会去比较这个modcount 是否与它取得的一致，否则就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。因为不同步可能引起死循环，造成GC问题。
注解3 ：关于putVal中出现的Node<K,V>
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
//存储一对映射关系的最小单元，也就是说key，value实际存储在Node中
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //节点的hash值
final K key;
V value;
Node<K,V> next; //指向的下一个节点,这里就是链表的实现机制
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
//所以直接输出hashmap的节点的时候的格式是 a=1 这种
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//内存地址相同（1.8新增）或者key-value完全相同表示为同一个值
public final boolean equals(Object o) {
if (o == this)//地址相同返回true
return true;
if (o instanceof Map.Entry) { //他是Map.Entry的实例且如果key-value相等返回true
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
/* jdk 1.6 Entry 的equals方法
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry)) //只要不是实例就返回false
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
} */
注解4 TreeNode<K,V>类里面的putTreeVal 这块打算以后写，其实就是tree版本的putVal
注解5 hash算法
主要为3步 - 取key的hashCode值、高位运算、取模运算
首先我们知道对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。
该对象应该保存在table数组的哪个索引处呢？我们可以再代码里看到：它通过hash & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
hash码 = (h = key.hashCode()) ^ (h >>> 16)
h=key.hashCode与h右移16位 做 按位异取1 同为0
然后在 (length-1)&hash 取得bucketInde
注解5 resize()方法-调整table大小用的
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
//返回的是一个新的table
final Node<K,V>[] resize() {
//先把原来的table 保存起来
Node<K,V>[] oldTab = table;
//旧的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的临界值
int oldThr = threshold;
//初始化新的值
int newCap, newThr = 0;
//当旧的表存在内容
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { //大于最大容量了2的30次方
threshold = Integer.MAX_VALUE; //临界值设值为Int最大值2的31次方
//不能扩容了返回原来的值
return oldTab;
}
//2倍原来的容量 和 2倍原来的临界阀值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // oldCap=0 ,oldThr>0，threshold(新的扩容resize临界值) 用临界值初始化容量值
newCap = oldThr;
else { // oldCap=0 ,oldThr=0 初次进来初始化容量值和临界值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { //新的阀值 计算新的上限
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //赋予新的阈值
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//根据新的容量设置新的桶
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //将原来桶中的值全部取出来进来放进新的bucket里面
Node<K,V> e;
if ((e = oldTab[j]) != null) {//当前桶里的值不为空 将以前的值赋给e
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 { // 如果存在链表的情况
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;//获取到下一个节点的值
//注解6
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;
}
}
}
}
}
return newTab;
}
注解6：
这里其实是看hash(key)最高位位是0还是1，因为当这里的&操作由原来的n-1变成了2n-1 其实就是最高位多了一个1 当hashkey的最高位也是1的时候就会改变index的值变成远来的index+oldCap的情况 这样就不用重新计算hash值 节省了时间。我的理解这里主要就是算法上的一个优化。跟原来1.7时候相比减少了碰撞，为什么呢？在1.7里面如果迁移表的时候，在新表里出现了数组位置相同的情况，那么就会把这个节点到该位置里单链表的尾部，在1.8这样的处理方法会使整个hashmap比较均匀，因为当最高位为1的index的位置是发生了改变的。
取出操作过程：
get 方法 -》调用的是getNode方法
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
然后我们来看看判断key是否存在方法
/**
* Returns <tt>true</tt> if this map contains a mapping for the
* specified key.
*
* @param key The key whose presence in this map is to be tested
* @return <tt>true</tt> if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;//只要返回值不等于null就返回true
}
然后问题来了
HashMap testMap=new HashMap<Integer,String>();
testMap.put(1,null);
System.out.println(testMap.containsKey(2));
System.out.println(testMap.get(1));
System.out.println(testMap.get(2));
会输出什么呢？
false （因为getNode返回的是一个value=null的Node，所以node!=null）
null
null
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {//判断hashmap存在值且该hash值与n-1计算得到的位置存在值
if (first.hash == hash && // 判断该位置的第一个值
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {//判断该位置是否存在链表/红黑树结构
if (first instanceof TreeNode)//红黑树
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {//链表
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//循环查找
return e;
} while ((e = e.next) != null);
}
}
return null;
}
/**
* Returns <tt>true</tt> if this map maps one or more keys to the
* specified value.
*
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {//遍历数组
for (Node<K,V> e = tab[i]; e != null; e = e.next) {//发现next不为空就查找该链表内容
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
网友评论