安杰小讲堂之HashMap（jdk1.7）

讲堂之HashMap（jdk1.7）"/>

安杰小讲堂之HashMap（jdk1.7）

代码总是猝不及防的。

HashMap<String,String> map =new HashMap<>();map.put("李靖", "嗲地");map.put("哪吒", "弟弟");map.put("金吒", "大弟弟");map.put("木吒", "二弟弟");map.put("三太子", "臭弟弟");for (String key: map.keySet()) {Integer hash =key.hashCode();System.out.println(String.format("%s的hash值是%s",key,hash));}

金吒的hash值是1178721
哪吒的hash值是695400
李靖的hash值是858568
木吒的hash值是840170
三太子的hash值是19928879

安杰老师在给小白江德华上课~~
安杰：HashMap 其实就是一个很简单的去存对象的容器。hashmap在1.7及1.7以前的版本中，内部数据结构使用的是数组+链表。既然用数组，那么我们对其进行操作时，肯定是需要它的下标值的。

德华：那它的下标值是它的hash值吗？
安杰：不是的。德华，你看上面的运行结果，它的hash值可有点大。
德华：😯，确实是，那嫂子，对它取模不是就会小一点吗？取模之后再作为下标标可以吗？
安杰：那我们来试一试~ 你先去叫你哥来学习。这个”执（zhi）绔（kua）子弟“，不思进取。

德华：哥，嫂子叫你学习了，你再不来，嫂子可就回娘家了😸!

for (String key: map.keySet()) {Integer hash =key.hashCode();int index =hash%8;System.out.println(String.format("%s的hash值是%s,index is ",key,hash)+index);}

金吒的hash值是1178721,index is 1
哪吒的hash值是695400,index is 0
李靖的hash值是858568,index is 0
木吒的hash值是840170,index is 2
三太子的hash值是19928879,index is 7

江德福晃晃悠悠地，拿着小板凳就来了~~
江德福：哟，这不是哪吒一家人嘛？最近挺好的？
安杰：闭上你的臭嘴，专心听课。（白眼）

安杰：你们看上面的运行结果，如果用取模之后的结果，作为下标值时，我们发现哪吒和李靖的值是一样的，当我们往数组中放他们时，就会发生碰撞。

江德福：哎，哪吒这个苦孩子，从出生他爹就看他不顺眼。
德华：可不是吗，他要能有俺哥这样的爹，那该多好…
（话音未落，德华感到背后一凉）
德华:嫂子你继续，嘿嘿。

安杰：当发生碰撞时，我们可以用一个链表指针来解决这种碰撞。（也可以用”再散列法“，也就是说当哪吒发现他的李靖爸爸已经占了它要放的那个位置时，哪吒可以被李靖牵着,也可以再去找一个没有人放的新地方。）
德华：（德华🙋‍♂️）嫂子，如果又有一个东海龙王取模之后，也是0，那么放在头部好，还是尾部好呢。

安杰：德华这个问题问的好。江德福，你多向你妹学学。别整天嘻嘻哈哈的。
江德福：好好好，你说的对，你俩什么时候倒成了一个战壕的姐妹了。😋您继续吧。

安杰：如果我们要放在尾部的话，我们得在这李靖的链上一直找，找到某各节点的next指针是null 时，才放，所以如果我们往头部放，这样性能就大大提高了。也就是东海龙王的next指针指向李靖，并且将东海龙王放在数组索引值的这个位置（即李靖原来的位置），三秒钟时间，你俩想想这个过程。

德华和江德福相视一笑，点点头。好像是懂了的样子。

安杰：嗯，不错，看来你俩是懂了。江德福，不愧是高级炮校的学员呢。
江德福：那是当然。

安杰：我们要put的时候就有两种情况，一种是key值相同，一种是key值不同。因此put时需先判断key值是否相同。（遍历链表）

相同时，返回oldvalue；
不同时，按照上面说的方法往里面添加元素。

get的话也是一样，需先遍历链表找到相同的key值，然后返回value，否则返回null。

安杰：那你来写一下它的put，get方法吧。
江德福：😕，写就写，老子害怕你不成？

public class MyHashMap<k,v> {class Entry<k,v>{public k k;public v v;public Entry<k,v> next;public Entry (k k,v v,Entry next){this.k =k;this.next=next;this.v=v;}private  Entry<k,v>[] table ;   //先定义存链表的数组private static Integer CAPACITRY;private static  Integer size;//构造函数public MyHashMap(){this.table=new Entry[CAPACITRY];}//数组的size方法public Integer size(){return size;}```

//get方法
public v get(k key){Integer hash =key.hashCode();Integer index =hash% table.length;for (Entry<k,v> entry=table[index];entry!=null;entry=entry.next ){if (key.equals(entry.k)){return  entry.v;}}return null;}

    //put方法public v put(k key, v value) {Integer hash =key.hashCode();Integer index =hash% table.length;for (Entry<k,v> entry=table[index];entry!=null;entry=entry.next ){if (key.equals(entry.k)){v oldvalue =  entry.v;entry.v=value;return oldvalue;} addEntry(key, value, index);}return null;}private void addEntry(k key, v value, Integer index) {table[index] = new Entry<k,v>(key,value,table[index]);size++;}}
}

安杰：嗯嗯，很不错。👍
江德福:(弱弱)今晚可以干革命吗~
安杰：滚。（江德福被一顿暴打）

安杰：我们来看看1.7中，HashMap的一些其他属性吧
指定初始容量 16
默认加载因子 0.75

阈值

接着再来看看他的实现吧

注意到有个init方法，但是注意这个init是空的，

这是给他的子类去用的。不细说了。接着继续看人家真正的put方法吧

其中inflaTable注意下：
capacity为什么需要>=传进去那个数的二的次方数呢，不应该传进去多少，他就是多大的吗？ 咱么先卖个关子。
德华：嫂子咋还卖上关子了。
江德福：你嫂子最近投资失败，把我我那些老本儿全赔了，就差砸锅卖铁了，卖关子还奇怪吗？
安杰默默不说话（毕竟不占理）。

（ 打破尴尬）

安杰：专心点儿，少说话。我们来把目光聚集到put方法的indexFor上，这就是它计算下标的方法。

我们看到他不是用它hash值取模的大小来确定下标的。 它是用的与操作。
这里咱们来看看。用16举栗子。

这样是能保证他的&结果是在0-15之内的，这也是上面为什么要取2的次方数的原因。
因为只有二的次方数才会是1之后任意0的形式。减一之后就是 0后任意个1。
至于hash值为什么要进行这么多的右移以及异或我就不深究了，你俩要是有兴趣 一个HashMap跟面试官扯了半个小时
我觉得人家写的超好，你俩可以看看
接着说人家的新增节点的操作 ,这里的threshold就是那个阈值。
可以看到 扩容有两个条件：
1、size>=阈值 ；
2、在数组的索引值处不是null；

扩容的话需要先创建一个新数组大小为原先数组大小的两倍。
然后将旧的值加到新数组。

安杰：你俩安分一点，坚持一下，这节课马上就结束了。
来看看他是如何将旧数组转为新数组
我们看到，有两个循环，遍历数组，遍历链表

这个时候就引出了最后一个问题。
在单线程下他是怎么工作的呢。
我们看图这是旧的数组。

这是将旧数组转化的新数组

我们看到了它的顺序在转移的时候发生了改变。
那么在多线程的时候他又会怎么样呢？
两个线程：A、B
开始时都将（1）作为自己开始转移的对象e，当线程A开始工作时，将A放到新数组对应位置之后，然后线程A认为的e已经指向了e.next （2）。然后A又将（2）又放到了新数组，next指向那个索引位置值（1）。
但是线程B认为的e依旧是原来的e，也就是（1），e的next是（2）。
如果这时候B醒了，就需要让自己的将自己的e放在索引位置（即现在（1）的位置），然后e又等于了e.next;这样的话是不是就死锁了呢。
所以它是线程不安全的。
那么jdk1.8是怎么对它进行优化的呢，咱们明天再看。要熄灯了。走吧江德福，干革命了。

晚安~ 好梦~