1. put方法过程中，计算出索引位置，如果存在值，则比较hashcode?到存在这一步不是已经说明了hashcode一样吗？

11 hashMap的putVal详解

1. 如何判断2个是相同的：
   ①hash(由key的hashcode ^ (hashcode >>> 16)得到)是否相等

   ②key 是否相等（比较两个对象的地址？） 或者 key的equals是否为true

2. e 和 p是什么？

12 putVal中的treeifyBin()方法

• 链表长度大于等于8，数组长度 < MIN_TREEIFY_CAPACITY = 64 ,进行扩容resize()
• 链表长度大于8，数组长度 >= 64,转为红黑树
  • 先将链表的每一个结点转为TreeNode类型(链表结点Node的子类)，并设置prev,next指针
  • table[index] 桶/数组结点从存的链表结点变为TreeNode的树根head
  • 调用head.treeify(tab) 进行 旋转 变为真正的红黑树

扩容机制

13 14

JDK1.8扩容时不再需要重新计算hash,但是元素的位置还是重新计算的，只是重新计算时比以前省去了计算hash值的时间，看hash值的高位是否为1，若为1，则新的索引为 原位置+旧容量

• 遍历原数组，如果元素Null,不做什么
• 如果元素next为null，直接剪切过去
• 如果元素Next为treenode类型，split红黑树
• 如果元素Next不为null,是个链表, 遍历链表计算元素新位置，copy过去

什么时候扩容？

• size > capacity * loadfactor
• 链表结点数 >=8 且 capacity < 64

remove删除

15

get方法讲解

16

map的4种遍历，一种不建议用

17

hashmap初始化容量采用阿里的推荐做法

18

1. HashMap的创建(1.7和1.8的区别)

2. HashMap的2个成员变量 负载因子 和初始容量

3. HashMap的put方法

   1. hash(key) 如何实现

   2. 什么时候发生冲突

   3. 怎样解决冲突？treeifyBin

   4. 1.7中新增节点采用头插法，1.8中新增节点采用尾插法。这也是为什么1.8不容易出现环型链表的原因。

4. HashMap的扩容

5. HashMap的rehash

   1.8rehash时保证原链表的顺序，而1.7中rehash时有可能改变链表的顺序（头插法导致）。

HashMap

JDK 8

1.key, value能null吗

都能。

2.数据结构

数组+链表+红黑树

3.默认容量

16 ,构造的时候不会初始化数组，会在put值进去的时候初始化容量为16的Node数组。

4.成员/属性

DEFAULT_INITIAL_CAPACITY = 1 << 4; DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始化容量 16

MAXIMUM_CAPACITY = 1 << 30 ; // 最大容量 2的30次方

DEFAULT_LOAD_FACTOR = 0.75f ; // 默认负载因子

TREEIFY_THRESHOLD = 8; // 链表转变为树的阈值 ，超过8转

UNTREEIFY_THRESHOLD = 6；// 树 转为 链表 的阈值，<6转

MIN_TREEIFY_CAPACITY = 64; // 

transient Node[] table; // //存储元素的数组
	:table就是HashMap中的数组，jdk8之前数组类型是Entry类型。从jdk1.8之后是Node类型。只是换	   了个名字， 都实现了⼀样的接⼝：Map.Entry

5.存储过程

6.核心方法put

难点要背

1.计算hash为什么要右移16位

2.table数组长度为什么要保持是2的指数次

3.什么是冲突？冲突判断为什么是那样的

Node old, Node new

old.hash == new.hash &&

​ (

​ new.key == old.key || ( new.key != null && new.key.equals(old.key))

​ )

当两个对象的hashCode相等会产⽣哈希碰撞，若key值内容相同则替换旧的value.不然连接到链表后⾯，链表⻓长度超过阈值8就转 换为红⿊树存储。

注: (Object)key值内容相同包括 对象地址相同 或者 对象地址不同但是内容相同(equals返回true).

还有一种情况，new.key 是null ，也就是hash都是0，相等。？这里还有点疑问

• 链表超过8个节点(实际是遍历到第8个结点，他的Next为构造的新节点，此时链表有9个节点)(泊松分布)，table数组容量>=64时才转为红黑树，否则先扩容。

• 链表节点插入方法：顺序遍历，尾插法。

7.扩容

扩容时机：

①table为空 -> resize

②插入到数组后 或者链表后 或者红黑树后，检查是否超过阈值，超过后扩容为原来的2倍，阈值也变为原来的2倍。

③链表节点超过阈值8，数组容量小于64时

扩容过程(伴随着rehash,但1.8巧妙的没有rehash)：

就是拷贝数组，

• 数组元素null的跳过
• 数组元素没有Next的直接拷贝到新数组相同索引处
• 用树处理冲突的：把树分开
• 用链表处理冲突的：看扩容后的高位是否为1，为1的话，新位置=原位置+旧容量，否则位置不变。

8.手写equals方法

① 先用==比较 地址，地址相同，对象相同

② 再用instance 判断类型，类型不同，对象不同

③地址不同，类型相同的时候，比较内容，内容相同，则对象相同：用Objects.equals比较两个对象（重写了equals用），基本类型用==。

9.hashCode equals == 的区别

== 基本类型比较的值，引用类型比较的是地址

equals 比较两个对象是否相同。

10.hashmap 和hashtable区别

11.hashmap是如何遍历的，为什么无序？

• entryset , keyset , 都会返回迭代器，都是继承Hashiterator.
• Hashiterator构造时，next属性为table数组从左到右第一个不null的Node

如何遍历？

next是第一个结点时

• 当前结点指向next所指结点，next指向下一个结点，下一个结点不空的话直接返回当前结点.
• 空的话,遍历table数组找到下一个不Null的Node

所以遍历是无序的(当然插入本来就是无序的)，遍历是从table数组左到右的顺序，有next的话会遍历Next.

12.treemap为什么是有序的？什么叫有序？

是个红黑树，是二叉搜索树吗？

• 是的。

为什么有序？

• 先通过keyIterator()拿到迭代器

• keyset遍历的时候先logn找到第一个结点（getFirstEntry() :最左结点)

• 然后调用nextEntry->succssor找后继

13.linkedhashmap又是如何保证插入顺序的？