HashMap
图片~~~
其他常见的map结构
常见的map结构
常用的Map结构有：hashMap(最常用)、hashTable、LinkedHashMap、TreeMap(对存入的键值进行排序)
LinkedHashMap和HashMap的区别
LinkedHashmap继承自hashMap，基于hashMap和双向链表实现
LinkedHashMap有序（插入有序和访问有序----默认为插入有序），hashMap则是无序
LinkedHashMap和hashMap都是基本entry[]存取数据
LinkedHashMap线程不安全
————————————————
需要的知识
hash和hashCode()
hashcode相等对象不一定相等，所以还要比较key的值
hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点，例如，java.util.Hashtable 提供的哈希表。
hashCode 的常规协定是：
在 Java 应用程序执行期间，在同一对象上多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
以下情况不 是必需的：如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。
实际上，由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的，但是 JavaTM 编程语言不需要这种实现技巧。）
当equals方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
1、hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的；
2、如果两个对象相同，就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相同；
3、如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点；
4、两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。
参考自~Java中hashCode的作用
一、HashMap简单介绍
1.8之前 （头插法）
数组是主体，链表的引入是当hashcode发生冲突的时候引入的
1.8之后（尾插法）
尾插法参考~HashMap的为啥用尾插法?
当主体长度大于64，链表长度大于8的时候（都要满足）
将链表转换为红黑树（平衡二叉树） 他都是基于效率来的
因为他们开发人员发现，即使链表长度大于8但是数组长度小于64的时候，转换为红黑树后遍历的效率并不会提升，反而会更麻烦
红黑树比链表查询速度快
特点：
- 存取无序的
- 键和值位置都可以是null，但是键位置只能是—个null
- 键位置是唯一的,底层的数据结构控制键的
- jdk1.8前数据结构是:链表＋数组jdk1.8之后是:链表＋数组＋红黑树
- 阈值(边界值)>8并且数组长度大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询
二、HashMap集合底层数据结构
通过将value转换成hashcode
hashCode = key.hashCode()
再使用算法将其作为数组下标把值放入
index = key.hashCode() & 桶.length
索引计算 HashMap 中 key 的存储索引是怎么计算的？先得到HashMap主体的长度length， 首先根据key的值计算出hashcode的值，然后根据hashcode计算出hash值，最后通过hash&（length-1）计算得到存储的位置。
hashcode是计算hash值的方法、返回对象的哈希码值。
hashcode相同但key不一定相同，可能存在不同的key映射到同一个位置
- .size表示 HashMap中K-V的实时数量，注意这个不等于数组的长度
- threshold(临界值)=capacity(容量)*loadFactor(加载因子)。这个值是当前已占用数组长度的最大值。size超过这个临界值就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。
- 所以size的长度永远小于桶大小的0.75
数据结构就是一种存储数据的结构
存储数据
在存储value1的时候，如果计算出的索引值为a，且此时的数组空间也存在索引为a的值value2，那么就会对已存在的值的hash值进行比较，若不同则在此空间上创建一个节点来存储value1
如果hash值相同，则发生哈希碰撞
底层就会调用key所属类的equals方法来判断内容是否相等
相等：覆盖
不相等：继续向下和其他数据的key比较，都不相等则在该空间画出一个新节点存储数据
三、底层源码
主要方法 putVal()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/* 关键 */
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 1st
treeifyBin(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 key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
tab就是hashmap的主体 - 数组
HashMap将链表转换为红黑树treeifyBin()方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 扩容 --------------------------
resize();
// 这一块儿就是转换成红黑树-----------------
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
面试题
1.哈希表底层如何计算hash值？还有哪些算法可以计算出hash值？
底层采用的key的hashCode方法的值结合数组长度进行无符号右移(>>>)、按位异或(^)、按位与(&)计算出索引。（效率高）
还可以采用:平方取中法，取余数，伪随机数法（效率较低）
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
2.面试题:当两个对象的hashCode相等时会怎么样?
会产生哈希碰撞，若key值内容相同则替换旧的value.不然连接到链表后面，链表长度超过阈值8就转换为红黑树存储。
3.面试题:何时发生哈希碰撞和什么是哈希碰撞,如何解决哈希碰撞?
只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。jdF8前使用链表解决哈希碰撞。jdk8之后使用链表+红黑树解决哈希碰撞。
4.面试题:如果两个键的hashcode相同，如何存储键值对?
hashcode相同，通过equals比较内容是否相同。
相同:则新的value覆盖之前的value
不相同:则将新的键值对添加到哈希表中
5.扩容问题
在不断的添加数据的过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式:扩容为原来容量的2倍，并将原有的数据复制过来。
6.何时变成红黑树
通过上述描述，当位于一个链表中的元素较多，即hash值相等但是内容不相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度(阀值)超过8时且当前数组的长度>64时，将链表转换为红黑树，这样大大减少了查找时间。jdk8在哈希表中引入红黑树的原因只是为了查找效率更高。
简单的来说，哈希表是由数组+链表+红黑树（IDK1.8增加了红黑树部分）实现的。
三、HashMap的继承关系
说明:
-
Cloneable空接口，表示可以克隆。创建并返回HashMap对象的一个副本。
-
.Serializable序列化接口。属于标记性接口。HashMap对象可以被序列化和反序列化。
-
.AbstractMap 父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。
-
补充:通过上述继承关系我们发现一个很奇怪的现象，就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢?同样在ArrayList中LinkedList中都是这种结构。
据java集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。