前言

map集合是key value的集合

HashMap与HashTable的区别

hashMap是线程不安全的，HashTable是读和写都加了synchronized锁，线程安全的，效率比较低，HashTabl不能存储key和value为null，HashMap可以存储key和value为null，存放在数组的第一个位置

HashCode的作用

hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值，主要应用于：HashMap能够快速查找
HashCode和Equals区别：两个对象的HashCode相同，但是对象不一定相同，如果equals相同，则Hashcode一定相同。

手写HashMap

自定义Map接口

package com.mayikt.ext;/*** @Description: 自定义Map接口* @Author: ChenYi* @Date: 2020/06/20 11:19**/
public interface MayiktMap<K, V> {/*** 集合的大小** @return*/int size();/*** 添加** @param key* @param value* @return*/V put(K key, V value);/*** 获取元素** @param key* @return*/V get(K key);/*** 存在的key和value的对象** @param <K>* @param <V>*/interface Entry<K, V> {K getKey();V getValue();V setValue(V value);}
}

基于ArrayList实现HashMap的代码 数组实现

package com.mayikt.ext.impl;import com.mayikt.ext.MayiktMap;import java.util.ArrayList;
import java.util.List;/*** @Description: 使用ArrayList实现自定义的HashMap* @Author: ChenYi* @Date: 2020/06/20 11:40**/public class MayiktArrayListHashMap<K, V> implements MayiktMap<K, V> {List<MayiktEntry<K, V>> mayiktEntryList = new ArrayList<>();@Overridepublic int size() {return mayiktEntryList.size();}@Overridepublic V put(K key, V value) {MayiktEntry<K, V> mayiktEntry = new MayiktEntry<>(key, value);mayiktEntryList.add(mayiktEntry);return value;}@Overridepublic V get(K key) {for (MayiktEntry<K, V> mayiktEntry : mayiktEntryList) {if (mayiktEntry.getKey().equals(key)) {return mayiktEntry.getValue();}}return null;}class MayiktEntry<K, V> implements MayiktMap.Entry<K, V> {private K k;private V v;public MayiktEntry(K k, V v) {this.k = k;this.v = v;}@Overridepublic K getKey() {return k;}@Overridepublic V getValue() {return v;}@Overridepublic V setValue(V value) {this.v = value;return v;}}
}

存在key相同并且哈希值相同的同一个对象，没有解决hash冲突的问题。

基于LinkList实现HashMap 链表实现

package com.mayikt.ext.impl;import com.mayikt.ext.MayiktMap;import java.util.LinkedList;
import java.util.Objects;/*** @Description:自定义基于LinkList实现HashMap* @Author: ChenYi* @Date: 2020/06/20 12:41**/public class MayiktLinkListHashMap<K, V> implements MayiktMap<K, V> {LinkedList<MayiktLinkListHashMap.MayiktEntry>[] data = new LinkedList[100];@Overridepublic int size() {return data.length;}@Overridepublic V put(K key, V value) {int index = hash(key);LinkedList<MayiktLinkListHashMap.MayiktEntry> linkedList = data[index];MayiktEntry<K, V> mayiktEntry = new MayiktEntry<>(key, value);//说明不存在该linkListif (Objects.isNull(linkedList)) {linkedList = new LinkedList<>();linkedList.add(mayiktEntry);data[index] = linkedList;return value;}//之前存在，需要遍历LinkList集合看是否存在key是否一样，如果一样修改value就可以了for (MayiktEntry entry : linkedList) {if (entry.getKey().equals(key)) {entry.setValue(value);return value;}}//存在hashCode冲突并且key不一样，需要加入一个新的linkedList.add(mayiktEntry);return value;}private int hash(K key) {int hashCode = key.hashCode();return hashCode % data.length;}@Overridepublic V get(K key) {if (Objects.isNull(key)) {return null;}int index = hash(key);LinkedList<MayiktEntry> linkedList = (LinkedList<MayiktEntry>) data[index];if (Objects.isNull(linkedList)) {return null;}for (MayiktEntry mayiktEntry : linkedList) {if (mayiktEntry.getKey().equals(key)) {return (V) mayiktEntry.getValue();}}return null;}class MayiktEntry<K, V> implements MayiktMap.Entry<K, V> {private K k;private V v;public MayiktEntry(K k, V v) {this.k = k;this.v = v;}@Overridepublic K getKey() {return k;}@Overridepublic V getValue() {return v;}@Overridepublic V setValue(V value) {this.v = value;return v;}}
}

HashSet源码解析

底层代码

  public boolean add(E e) {return map.put(e, PRESENT)==null;}

HashSet底层是基于HashMap实现的，添加的值作为HashMap的Key,里面创建了一个对象来作为value，起到占位符的作用，因为HashMap不允许key重复，所以HashSet的值也是唯一的。

1.7HashMap的原理

下面展示一些 内联代码片。

jdk1.7的HashMap代码

package com.mayikt.ext.impl;import com.mayikt.ext.MayiktMap;import java.util.HashMap;/*** @Description: 1.7HashMap类* @Author: ChenYi* @Date: 2020/06/21 20:57**/public class MayiktHashMap<K, V> implements MayiktMap<K, V> {/*** 默认的初始化容量*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;/*** 默认的加载因子*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 最大的容量*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** 实际的加载因子*/final float loadFactor;/*** 阈值*/int threshold;/*** 空的数组*/final MayiktHashMap.Entry<?, ?>[] EMPTY_TABLE = {};/*** 数组*/transient MayiktHashMap.Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;transient int hashSeed = 0;transient int size;transient int modCount;public MayiktHashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}public MayiktHashMap(int initialCapacity, float loadFactor) {//设置初始容量if (initialCapacity < 0) {throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);}if (initialCapacity > MAXIMUM_CAPACITY) {initialCapacity = MAXIMUM_CAPACITY;}if (loadFactor <= 0 || Float.isNaN(loadFactor)) {throw new IllegalArgumentException("Illegal load factor: " +loadFactor);}//设置实际的加载因子this.loadFactor = loadFactor;//实际的容量threshold = initialCapacity;init();}protected void init() {}@Overridepublic int size() {return 0;}@Overridepublic V put(K key, V value) {//第一次添加元素if (table == EMPTY_TABLE) {inflateTable(threshold);}//如果key为nullif (key == null) {//添加key为nullreturn putForNullKey(value);}//hash值int hash = hash(key);//计算数组中的索引位置int index = indexFor(hash, table.length);//遍历Entry，判断是不是同一个key,如果是同一个key则修改值for (MayiktHashMap.Entry<K, V> e = table[index]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;return oldValue;}}//添加元素addEntry(hash, key, value, index);size++;return null;}private V putForNullKey(V value) {//如果之前存在为null的时候，需要修改值for (MayiktHashMap.Entry<K, V> e = table[0]; e != null; e = e.next) {if (e.key == null) {V oldValue = e.value;e.value = value;
//                e.recordAccess(this);return oldValue;}}modCount++;addEntry(0, null, value, 0);return null;}void addEntry(int hash, K key, V value, int bucketIndex) {//看是否需要扩容if ((size >= threshold) && (null != table[bucketIndex])) {//扩容，扩大两倍resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);}/*** 扩容** @param newCapacity*/void resize(int newCapacity) {MayiktHashMap.Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}MayiktHashMap.Entry[] newTable = new MayiktHashMap.Entry[newCapacity];transfer(newTable, false);table = newTable;threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}/*** 扩容之后重新赋值** @param newTable* @param rehash*/void transfer(MayiktHashMap.Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (MayiktHashMap.Entry<K, V> e : table) {while (null != e) {MayiktHashMap.Entry<K, V> next = e.next;//重新计算索引indexint i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}}private void createEntry(int hash, K key, V value, int bucketIndex) {//如果没有发生hash冲突，取出来为null,如果发生hash冲突，采用头插法，新添加的要放在前面Entry<K, V> next = table[bucketIndex];//设置数组中索引的entry对象table[bucketIndex] = new MayiktHashMap.Entry<>(hash, key, value, next);}/*** 根据hash值和数组长度计算对应的数组索引** @param hash* @param length* @return*/static int indexFor(int hash, int length) {//length都是2的幂次方偶数，为了减少index冲突，所以需要减1，变成基数，这个是计算机的位运算return hash & (length - 1);}/*** 计算hash** @param k* @return*/final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}private void inflateTable(int toSize) {//设置初始容量为2的幂次方，都是偶数来的int capacity = roundUpToPowerOf2(toSize);threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);table = new MayiktHashMap.Entry[capacity];
//        initHashSeedAsNeeded(capacity);}private static int roundUpToPowerOf2(int number) {// assert number >= 0 : "number must be non-negative";int rounded = number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (rounded = Integer.highestOneBit(number)) != 0? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded: 1;return rounded;}@Overridepublic V get(K key) {if (key == null) {return getForNullKey();}MayiktHashMap.Entry<K, V> entry = getEntry(key);return null == entry ? null : entry.getValue();}/*** 获取key为null的值** @return*/private V getForNullKey() {if (size == 0) {return null;}for (MayiktHashMap.Entry<K, V> e = table[0]; e != null; e = e.next) {if (e.key == null) {return e.value;}}return null;}private Entry<K, V> getEntry(K key) {if (size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);for (MayiktHashMap.Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {return e;}}return null;}static class Entry<K, V> implements MayiktMap.Entry<K, V> {final K key;V value;MayiktHashMap.Entry<K, V> next;int hash;/*** Creates new entry.*/Entry(int h, K k, V v, MayiktHashMap.Entry<K, V> next) {value = v;this.next = next;key = k;hash = h;}@Overridepublic final K getKey() {return key;}@Overridepublic final V getValue() {return value;}@Overridepublic final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}}
}

总结：

• 底层是基于数组+链表来实现的，通过使用Entry对象来存储key和value值，并且Entry是一个单向链表，只记录下个节点的指针，没有记录上一个的节点的指针
• 默认的初始容量是16，加载因子是0.75
• 支持key为null的存放，存放在数组中索引为0的位置，第一个位置
• 数组的长度都是2的幂次方，偶数来的，即使在new出一个HashMap指定的初始容量为奇数的时候，但是在第一次添加元素的时候会通过计算，取离当前指定容量最小的2的幂次方作为数组的容量，比如当前指定数组为3，则取4，如果为9则取16
• 为了减少数组index冲突,使用了hash & (length - 1)的位运算，因为length都是偶数，为了减少index冲突，所以减1变成奇数，这样在进行与运算的时候能够减少index冲突
• 为了能够充分利用资源，在达到扩容的阈值的时候，准备resize的时候，还需要判断对应的数组索引有没有发生冲突了，如果没有的时候不会扩容先，(size >= threshold) && (null != table[bucketIndex])，扩容都是扩大两倍
• 数组的长度扩大两倍之后，还需要调用transfer函数进行计算新的index值，放到扩容后的数组中
• load_factor加载因子为0.75的原因，因为如果加载因子很大的时候，说明阈值很大，数组快要满的时候才进行resize，这个时候发生index冲突很多，如果加载因子过小的时候，阈值比较小，很快就会扩容，数组的空间内存不能够充分的利用，为了保证冲突的机会和空间利用率之间保持一种平衡，所以使用0.75是最好的
• put方法的实现先计算出key的哈希值，然后再通过indexFor方法计算出在数组中的索引位置
• index冲突和hash冲突的区别，index冲突是因为底层使用二进制运算产生相同的index,对象不同，但是二进制产生相同的index,hash冲突对象不同，但是hashCode相同
• 根据key查询的时间复杂度
  1.如果该key没有发生hash冲突，直接根据index从数组中获取，时间复杂度为O(1)
  2.如果该key发生了hash冲突，则需要从链表中查询，查询效率比较慢

jdk7存在的问题

• 线程不安全，链表如果过长，会导致查询效率低，时间复杂度O(n)
• 扩容的时候会存在死循环的问题
  1.当在多线程的情况下，同时对HashMap实现扩容，因为每次数组在扩容的时候，新的数组长度发生了变化，需要重新计算index值，需要将原来的table中的数据移动到新的table中,e.next=new Table[i],操作的是共享变量，因为之前是同一个链表的，重新计算index值的时候还是会在同一个链表中的（hash值是不变的），如之前是B-A,然后两个线程进行同时操作，由于是采用的是头插法，当线程1重新计算index完成并且已经把指针改成A-B,但线程2这个时候才开始计算，这个时候B-A-B,就会造成循环引用，死循环了。
• jdk7中的hashMap计算hash非常均摊，减少hash冲突问题，降低查询效率
• jdk8中的hashMap计算hash非常简单，存在hash冲突的概率比较大，但是jdk8使用了红黑树解决了查询效率慢的问题

jdk8HashMap

总结：

• 底层是才有数组+链表+红黑树（一种平衡二叉树）来实现的，时间复杂度是O(logn)
• 计算hash的函数比较简单，因为当发生了冲突之后，会才有红黑树来存储，不会导致链表过长，查询效率降低
• 当链表的长度超过8的时候，并且数组的容量大于64的情况下链表才会转为红黑树，如果链表长度超过了8但数组的长度没有超过64的时候只是会扩容，容量扩大两倍，超过了64的情况下就会将整个单向链表转换成双向链表，再将整个双向链表转成红黑树
• 扩容的时候会重新计算index值，但是注意之前是同一个链表的还是会在同一个链表中，因为同一个链表hash值都是相同的，经过index= (n - 1) & hash
  计算处理的index都是相同的，所以扩容的时候如果之前是同一个链表的，扩容之后也是在同一链表的
  如果链表的长度小于6的情况下，红黑树就会变成链表

ConcurrentHashMap源码

1.7

• 默认分成了16个Segment,采用了分段锁，每个Segment有独立的table,Segment继承了ReentrantLock的重入锁，HashEntry来存储数据
• 根据key计算index存放在Segment位置

1.8

• 采用了cas无锁机制
• 使用Node节点来存储数据，new Node采用了cas乐观锁机制保证线程安全性的问题
• 如果计算index产生了冲突，使用synchronized上锁
• 锁的粒度比jdk1.7更加精细

参考：来自蚂蚁课堂