源码解析 HashMap底层实现和原理 _数组

Note：文章的内容基于JDK1.7进行分析，1.8做的改动文章末尾进行讲解。
大家可以看一下:
一、先来熟悉一下我们常用的 1、概述
基于Map接口实现，元素以键值对的方式存储，并且允许使用null 建和null值，因为key不允许重复，因此只能有一个键为null,另外不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。是线程不安全的。
2、继承关系
public class HashMapextends AbstractMapimplements Map, Cloneable, Serializable
3、基本属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16 static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子0.75static final Entry[] EMPTY_TABLE = {};//初始化的默认数组transient int size;//HashMap中元素的数量int threshold;//判断是否需要调整HashMap的容量
Note：的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。的线程是不安全的，多线程环境中推荐是。
二、常被问到的和的区别 1、线程安全
两者最主要的区别在于是线程安全，而则非线程安全。
的实现方法里面都添加了关键字来确保线程同步，因此相对而言性能会高一些，我们平时使用时若无特殊需求建议使用，在多线程环境下若使用需要使用.()方法来获取一个线程安全的集合。
Note：
.()实现原理是定义了一个的内部类，这个类实现了Map接口，在调用方法时使用来保证线程同步,当然了实际上操作的还是我们传入的实例，简单的说就是.()方法帮我们在操作时自动添加了来实现线程同步，类似的其它.方法也是类似原理。
2、针对null的不同
可以使用null作为key，而则不允许null作为key
虽说支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事。
Note：以null作为key时，总是存储在table数组的第一个节点上。
3、继承结构
是对Map接口的实现，实现了Map接口和抽象类。
4、初始容量与扩容
的初始容量为16，初始容量为11，两者的填充因子默认都是0.75 。
扩容时是当前容量翻倍即:*2，扩容时是容量翻倍+1即:*2+1 。
5、两者计算hash的方法不同
计算hash是直接使用key的对table数组的长度直接进行取模
int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;
计算hash对key的进行了二次hash，以获得更好的散列值，然后对table数组长度取摸。
int hash = hash(key.hashCode());int i = indexFor(hash, table.length);static int hash(int h) {// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}static int indexFor(int h, int length) {return h & (length-1);
三、的数据存储结构 1、由数组和链表来实现对数据的存储
采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。
数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。
从上图我们可以发现数据结构由数组+链表组成，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key.())%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12=12,28=12,108=12,140=12 。所以12、28、108以及140都存储在数组下标为12的位置。