hashmap是我们常用的容器类，但是为什么会有这种数据结构出现呢？它是怎么操作的呢？本文会带你领略大神的编程。
为什么要有hashmap？
我们已经有了数组，ArrayList和LinkedList，为什么要有HashMap？ 因为在之前的数据结构中，最好的搜索方法是有序数组的二分查找和AVL树搜索。它们的最坏情况所搜时间都是O（lgn）。是否有更快的算法？散列表数据结构提供了这样的保证——O(1)的平均搜索时间。
本文的内容结构为
1、HashMap 存储结构
2、HashMap 各常量、成员变量、内部类作用
3、HashMap 几种构造方法
4、HashMap put 及其相关方法
5、HashMap get 及其相关方法
6、HashMap remove 及其相关方法
7、HashMap 扩容方法resize()
一、HashMap 存储结构
先来看一下 HashMap 的继承图：
HashMap 根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。HashMap 最多只允许一条记录的键为 null ，允许多条记录的值为 null 。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap，可能会导致数据的不一致。
我们再来看一下HashMap的实现方式
HashMap是数组 链表 红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示：
二、HashMap 各常量、成员变量作用
常量
代码语言：javascript复制 //创建 HashMap 时未指定初始容量情况下的默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap 的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时，进行 resize() 操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//用来确定何时将解决 hash 冲突的链表转变为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 用来确定何时将解决 hash 冲突的红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;
//当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于 MIN_TREEIFY_CAPACITY ）导致的 hash 冲突太多，
//则不进行链表转变为红黑树操作，转为利用 resize() 函数对 hashMap 扩容
static final int MIN_TREEIFY_CAPACITY = 64;变量
代码语言：javascript复制 //保存Node<K,V>节点的数组
transient Node<K,V>[] table;
//由 hashMap 中 Node<K,V> 节点构成的 set
transient Set<Map.Entry<K,V>> entrySet;
//记录 hashMap 当前存储的元素的数量
transient int size;
//记录 hashMap 发生结构性变化的次数（注意 value 的覆盖不属于结构性变化）
transient int modCount;
//threshold的值应等于 table.length * loadFactor, size 超过这个值时进行 resize()扩容
int threshold;
//记录 hashMap 装载因子
final float loadFactor;内部类
代码语言：javascript复制// Node<K,V> 类用来实现数组及链表的数据结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //保存节点的 hash 值
final K key; //保存节点的 key 值
V value; //保存节点的 value 值
Node<K,V> next; //指向链表结构下的当前节点的 next 节点，红黑树 TreeNode 节点中也有用到
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
// TreeNode<K,V> 继承 LinkedHashMap.Entry<K,V>，用来实现红黑树相关的存储结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 存储当前节点的父节点
TreeNode<K,V> left; //存储当前节点的左孩子
TreeNode<K,V> right; //存储当前节点的右孩子
TreeNode<K,V> prev; // 存储当前节点的前一个节点
boolean red; // 存储当前节点的颜色（红、黑）
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
} 三、HashMap 几种构造方法 hashmap初始化时为懒加载方式，即在初始化时仅声明容量及扩容阈值等， 不多说上代码。
代码语言：javascript复制
//构造方法１，指定初始容量及装载因子
public HashMap(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;
/** tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂，
* 若指定初始容量为９，则实际 hashMap 容量为16
*/
this.threshold = tableSizeFor(initialCapacity);
}
//构造方法２，仅指定初始容量，装载因子的值采用默认的 0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造方法３，所有参数均采用默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
重要说明 此方法意为传一个期望值返回一个最接近期望值的2的幂。
代码语言：javascript复制
//tableSizeFor(initialCapacity) 方法返回的值是最接近 initialCapacity 的2的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
/**
* 以下表达式为 n的二进制与 n的二进制数右移后x位的结果进行异或
* 目的是保证高位1后的数据均为1,普及一下如果高位1后面全是1的话，
* 即 0000 0000 0000 0000 0000 0000 0000 1111
* 这样的二进制表示为 15，可以推导出 为2的幂-1。
* 至于为何 右移 1 2 4 8 16 = 31位
* 是因为一个 Integer 类型占 4 字节，一个字节占 8 位二进制码，
* 因此一个 Integer 总共占 32 位二进制码。去除第一位的符号位，
* 剩下 31 位来表示数值。所以右移31位，以此保证高位1后面的数据均为1。
*/
n |= n >>> 1;// >>> 代表无符号右移
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
/**
* 当n小于 最大值时
* 返回 n 1，由上面我们知道 如果高位1后面全是1的话，
* 用十进制表示为 2的n次方-1,所以返回的n 1 则为
* 2的n次方，这就是为什么hashmap的容量必须会是2的n次方
*/
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}内容太多，更多精彩请期待
