以前一直没有做技术沉淀，最近闲下来了面试了挺多公司，作为一名有着快6年开发经验的java程序员来说，我最近被面试官说得最多的一句话就是很多东西两年左右开发的都懂。
所以我就打算开始编写底层业务的说明，说做就做。
面试常问的问题1、HashMap、HashTable、TreeMap的区别以及实现原理。
首先我们先说Hash(哈希、散列)
Hash
Hash就是将任意长度的对象，通过散列算法变换成固定长度的输出，该输出的值称之为散列值(Hash)，这种转换方式是一种压缩映射，也就是说hash值的空间通常远远小于输入的空间，不同的输入对象可能会散列成相同的hash值。所以不能从散列值来唯一的确定输入的值，如果出现不同输入对象生成相同的hash值时，称之为hash碰撞
下面简单讲解一下两个不同对象的hash算法:
Integer-int类型获取的hash值是其自身的value
String类型获取Hash值的方案是:
// 底层HashCode实现原理
// 首先设定一个默认的hash值 默认为0
int hash = 0;
// value 为char[] char数组(在Java中String的解决方案是将字符用字符数组形式进行设定
// 也就是说其实我们在设定字符串的时候是生成了一个字符数组)
// 如果当前的hash值是0 且值的长度大于0
if (hash == 0 && value.length > 0) {
// 将当前的字符数组进行复制，用于有效且方便的重新计算当前的hash值
char val[] = value;
// 循环遍历当前的字符数组 并进行加法计算之前的值
for (int i = 0; i < value.length; i++) {
// 便于读者阅读，所以将当前算法进行详解
// 在字符串中的算法设定中，当前的hash值是当前的字符，也就是说其实是将整个
// char[] 数组进行设定为每一个对应的hash值
int thisHash = val[i];
// 历史hash 用于进行字符添加方案，需要进行历史hash值重新设定，* 31 也就是进行数据位移
int oldHash = 31 * hash;
// 最后将当前的hash 也就是 val[i] 与重新设定的历史hash 31 * hash 进行相加 生成新的hash值
hash = thisHash + oldHash;
}
}
return hash;
相对应的获取方案就不一一编写了，读者可以自行查询源码。
常见的hash函数设定方案有一下几种:
1、直接定址法: 直接以关键字k或者k加上某一个常数(k + c) 作为hash值。
2、数字分析法: 提取关键字中取值相对均匀的数字作为hash值。
3、 除留余数法: 用关键字k除以某个不大于hash表长度m的数p,将所得的余数作为hash值。
4、分段叠加法: 按照哈希地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的hash值。
5、平方取中法: 如果关键字各个部分分布都不均匀，可以先求出其平方值，然后按照需求取中间几位作为hash值。
6、伪随机数法: 采用一个伪随机数作为hash值。
HashMap
HashMap继承自AbstractMap，抽象Map，其是所有map的抽象父类。AbstractMap设定了Map的方法以及其获取值以及键的方案。
HashMap中设定了一个内部类为Node(节点)，其引用了Map.Entry接口
设定的属性为hash、key、value、next
也就是在这里HashMap就将其存储方案进行了设定，其是将所有的键值都存放在Node之中，且为设定存储方案存入下一个值的next同样为当前的Node对象
也就是说HashMap的存储方案是以一个链表结构进行的数据存储
接下来HashMap为了方便其获取hash值,编写了一个静态方法hash(Object key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在这里我们能看出其在设定的时候key的设定也就是可以为null值，也就是说如果key为null是，将设定当前的hash为0 否则获取其本身的hash并进行向右偏移16位与当前的hash值进行位运算
从主观而言，我们了解了以上两点之后需要了解到的解释hashmap的put 与get方法了
先说说put方法,put方法只是一个对外我们常用的方法，而内置的关联方法为putVal方法
/**
* Implements Map.put and related methods
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict);
在我们使用put方法时实际内置调用的是putVal方法。我们可以过滤掉后面两个boolean类型参数，在put方法调用putVal方法时，onlyIfAbsent = false，evict = true。
在putVal方法调用时其声明了一个Node<K, V>[] tab;其是整个HashMap的核心数据链表对象
声明了一个Node<K, V> p; 其是用于作为当前键值对的数据存储对象。
声明了两个int整数 n、i
n用于设定整个链表的长度 而i用于设定其索引位置即index
其首先判断了tab是否为空 或 tab的长度等于0的情况 并对tab与链表长度参数n进行赋值
如果当前链表是空的或长度为0时则初始化tab并将其长度重新赋值
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 然后判断当前链表的上一级hash是否存在，并获取上一级的Node节点赋值给p
if ((p = tab[i = (n - 1) & hash]) == null) {
// 如果上一节点为空 则创建新的一个简单，并将当前的键值对设定给新的Node 即结束当前put方案
tab[i] = newNode(hash, key, value, null);
} else {
// 否则重新声明一个Node 以及key
Node<K, V> e; K k;
// 如果上一节点的hash等于当前存在的hash 且整个key与上一节点相同时 将上一节点p赋值给当前节点e
if (p.hash == hash && ((k = p.key) == key || key != null && key.equals(k))){
e = p;
} else if (p instanceof TreeNode ){
// 如果上一节点p是树状节点 TreeNode的实例时
// 则将当前实例添加到树状节点中 (HashMap另一套存储方案 红黑树存储实现方案)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
} else {
// 循环Node 进行数据遍历
for (int binCount = 0; ; ++binCount) {
// 直到当前节点为空时将当前节点赋值
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果当前节点长度为8时重新创建一个Node树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果当前的hash与上级hash相同时直接跳过 进行下一次循环获取树节点信息
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
// 如果当前节点不等于空则 且key存在的情况时重新value赋值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果当前的size过大时进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
