前言
- 前面四篇说了线性表和链表，并且也手写了其中一些的实现原理，我们先说说他们的数据结构
数组：它采用了连续的内存存储空间，对于指定下标的查找，时间复杂度尾O(1),通过给定值进行查找，需要将一个一个的遍历，时间复杂度为O(n),对于一般的查找和删除，数组元素需要移动，时间复杂度尾O(n)
线性链表：而对于链表之间的插入和删除，仅仅处理链表结点之间的关系就行，时间复杂度尾O(1),但是对于查找的话，要一个结点一个结点进行对比，时间复杂度尾)(n)
那么有没有一种结构既可以支持随机访问，并且插入和删除的效果高呢，那么肯定是有的 就是HashMap，它内部实现了一张hash表。我们就来看看它是怎么玩的
HashMap
特点：hash表又叫散列表，是一种非常重要的数据结构，应用场景非常丰富，比如缓存技术的核心就是内部维护了一张强大的hash表，并且hashmap的实现原理也是许多面试经常问的。它对数据的插入、删除、查找、性能非常的高，不考虑hash冲突的情况下，仅仅只需用hasn函数算出位置就可以找到要找的元素，那么它内部是怎么实现的 我们接着来看看。
实现原理
1、数据结构的物理存储结构有两种：一种是数组一种是线性链表，而上面说的一次性定位，肯定是只有数组才能做到一次定位元素，没错hashmap的主干就是数组，所以我们要插入或者查找元素，我们可以通过hash函数算出下标，一次性就可以定位到元素，那么我么就可以得到存储位置=f(x) 这里的f(x) 是可以自定义的，当然系统肯定是有人家自己的。
2、hash冲突
然而上面这张图是有问题，假如我们要插入两个不同元素，但是我们通过hash函数算出两个存储的地址相同咋办，不用问，肯定是有这种可能性的，那么这种被称为hash冲突也叫hash碰撞。所以我们说一个好的hash函数是非常重要的，他能够尽量的保证计算简单和散列地址分布均匀。但是我们知道数组是一片连续的存储空间，再好的hash函数也避免不了碰撞，那么是如何解决呢。
3、hash冲突解决方案
hash冲突解决方案有多种：开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），在散列函数法，链地址法，而hashmap是用了链地址法，也就是数组+链表
4、图解分析
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
上图还有这个源码可以看出，hashmap内部是维护了一个实体entry，那么这个entry就是每个结点，里面包含了我们存的key和value，还有计算的hash值，还有下一个结点，那么它就是
源码解析
1、先看hashmap几个重要的字段
transient int size;实际存储的key-value键值队的个数
int threshold;阈值，当table为空的时候，是初始数量，默认为16，当table被填充， 一般就是capacity*loadFactory 后面会说到。
final float loadFactor；是一个负载因子，代表了table的填充度，默认是0.75 一般是0.6到0.9之间最佳
hashmap有4个构造器，看一个比较重要的构造器
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
//此处对传入要初始的大小进行校验不能大于1<<30 也就是2的30次幂
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init(); //init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}
看了半天这构造器里面也没有创建数组啊 不要急 hashmap是在put方法才会创建的 （有一个构造方法会创建），那么我们就来看看put方法
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);//看到没这个函数 这个就是系统为我们系统的hash函数
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
我们在来看看inflateTable这个方法
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
inflateTable这个方法主要是用于为数组在内存中进行分配空间的 通过roundUpToPowerOf2(toSize)可以确保capacity为大于或者等于toSIze的二次幂，比如toSize为13则capacity为16 ，就是通过下面这个算法来实现的
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
还有这个方法是通过hash值和table.length-1来& 这样得到的值永远不会大于数组的大小，当然也可以取模 但是取& 效率更高一点。
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
再来看看addEntry这个方法
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容 并且扩容的数量为两倍的扩
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
这是createEntry方法
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
//这里就是将Entry插入到bucketindex这个位置
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
那么为什么扩容一定是2的次幂呢 我们来看看resize这个方法（扩容是一个非常消耗资源的操作，所以平时我们可以预估一下我们的hashmap存多少数据，调用它的设置大小的构造方法 这以前我也是不知道。。。。）
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
再来看看transfer这个方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//for循环中的代码，逐个遍历数组，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
这个方法是将老数组中的数据逐个遍历，复制到新的扩容后的数组，数组的索引位置的计算是通过key值通过hash函数运行后和length-1进行&运算得到的。
hasnMap的数组长度要保持2的次幂，比如16的二进制表示为100000，呢么length-1就是15，二进制是01111，同理扩容后的数组长度为32，二进制1000000，length-1为31 二进制为011111，从下图我们也能看出，这样能保证最低位都是1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过h&(length-1) 的时候，只要h对应的最左边的哪一个差一位是0，这样就能保证得到的新数组索引和老数组索引一致（减少了之前已经散列的老数组的数据位置重新调换）我是这么理解的
还有，数组的长度保持2的此幂，length-1的低位都是1，会使得获得的数组索引index更加均匀
再来看看get方法
public V get(Object key) { //如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
看看getEntry
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
for (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;
}
- hashMap源码就分析到这里了 里面重要的方法和逻辑结构也就这些了 至于 删除和修改也都是 在上面分析的源码有体现
手写hashMap实现
public class HashMapDemo<K, V> {
//默认的数组的大小
private int DEFAULT_CAPACITY = 16;
private int length;//数组中真实存储的大小
private HashMapDemoEntity<K, V> mTable[] = new HashMapDemoEntity[DEFAULT_CAPACITY];
public void put(K k, V v) {
if (k == null) {//这里就不支持存null为key了
return;
}
int hash = getHash(k);
int index = hash & length;//得到的是一个位置
HashMapDemoEntity<K, V> entity = mTable[index];
if (entity != null) {
//这里证明该数组下标处存了值
HashMapDemoEntity<K, V> newEntity = new HashMapDemoEntity<>(k, v, hash, entity);
//然后将
mTable[index] = newEntity;
//这是链表里面的 但是这里写的是存的值是可以唯一的
}
addEntity(index, hash, k, v);
}
public V get(K k) {
if (k==null){
return null;
}
HashMapDemoEntity<K,V> entry = getEntry(k);
return null == entry ? null : entry.getValue();
}
private HashMapDemoEntity<K, V> getEntry(K key) {
int hash = key.hashCode();
for (HashMapDemoEntity<K,V> e = mTable[hash&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;
}
private void addEntity(int index, int hash, K k, V v) {
//这里添加涉及到扩容
HashMapDemoEntity<K, V> e = mTable[index];
mTable[index] = new HashMapDemoEntity<>(k, v, hash, e);
}
public int getHash(K k) {
return k.hashCode();//hasn函数 得到一个hash值
}
/**
* 这个就是一个内部维护的静态内部类
*
* @param <K>
* @param <V>
*/
private static class HashMapDemoEntity<K, V> {
K key;
V value;
int hash;
HashMapDemoEntity<K, V> next;
public HashMapDemoEntity(K k, V v, int h, HashMapDemoEntity<K, V> n) {
this.key = k;
this.value = v;
this.hash = h;
this.next = n;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
}
