目录
一、序言二 、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