目录
一、序言二 、HashMap原理分析二、HashMap和Hashtable区别？一、序言
作为Android程序员，出去找工作面试，HashMap应该是最常被问到的一种数据类型。那它是怎么实现的呐？我们都知道，数据结构中有数组和链表来实现对数据的存储，这两者是两个极端。数组存储区间是连续的，占用内存严重，但查询效率高；而链表存储区间是离散的，占用内存较小，但时间复杂度高，查询复杂。有没有结合两者特性，既寻址容易、也插入删除简单的数据结构呢？答案是肯定的，哈希表（Hash table）就是其中之一。哈希表最常用的一种实现方式是——拉链法，可以把它看作“链表的数组”。
二 、HashMap原理分析
Hashmap存储数据的容器也是一个线性数组，它具有一个静态内部类Node，数据结构如下：
static class Node<K,V> implements Map.Entry<K,V> {final int hash; //对Key计算的hash值final K key; //KeyV value; //valueNode<K,V> next; //链表指向的下一个Node}
存储时：
int index = (length - 1) & hash(key); // hash值与Node长度取模，得到数组下标Node[index] = value;
取值时：
int index = (length - 1) & hash(key); // hash值与Node长度取模，得到数组下标return Node[index];
其中的hash方法在java8中实现如下：
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
这个“扰动”函数的价值是：将hash值右移16位(刚好32bit的一半)，然后让自身的上半区与下半区做“亦或”操作，为的是加大低位的随机性，再与Node长度取模，做为下标，可以有效减少碰撞次数。
那么，两个key的hash值取模得到相同的index，会不会把前一个node覆盖呢？
这里就用到了hashmap的链式结构了，Node里面有一个next属性，指向下一个Node。例如，进来一个键值对A，对keyhash取模得到index=0，则Node[0]=A，有进来一个键值对B，得到对index也为0，hashmap这样处理，B.next=A，Node[0]=B，这时又进来一个C，同样index=0，则C.next=B，Node[0]=C。我们发现 数组中总是存放最新的一个Node元素
HashMap是如何根据Key取出value的呢？ 我们看一段代码
public V get(Object key) {int hash = hash(key.hashCode());//先定位到数组元素，再遍历该元素处的链表Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {do {if (e.hash == hash &&((k = e. key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}
二、HashMap和Hashtable区别？
1.HashMap支持null Key和null Value；Hashtable不允许。这是因为HashMap对null进行了特殊处理，将null的hashCode值定为了0，从而将其存放在哈希表的第0个bucket。2.HashMap是非线程安全，HashMap实现线程安全方法为Map map = Collections.synchronziedMap(new HashMap())；Hashtable是线程安全3.HashMap默认长度是16，扩容是原先的2倍；Hashtable默认长度是11，扩容是原先的2n+14.HashMap继承AbstractMap；Hashtable继承了Dictionary
