哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，本文会对java集合框架中的对应实现HashMap的实现原理进行讲解，然后会对JDK7的HashMap源码进行分析。
在了解hashMap我们先了解几个面试会遇到的问题：
1.HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。
2.非同步，线程不安全。
3.底层是hash表，不保证有序(比如插入的顺序
4.hash值相等，两个对象不一定相等；两个对象不相同，hash值可能相同；
5.hashMap数据结构是数组+单链表,扩容因子为0.75 过大导致数据过于密集 查询速度降低 过小扩容频繁 浪费内存
put过程：
1、执行hash(Object key)得到hash值，根据 hash 值找到其所在的数组的角标位置index
2、再去遍历该桶里面的链表判断是否有 key 相同，如果有则覆盖
3、key不同则产生hash碰撞 需要将值插入到链表里面
4、在插入值之前需要首先需要判断是否进行扩容（1.8里面先插入再扩容）插入这个值是否导致size已经超过了阈值，是则进行扩容
为加深印象先看看结构图
image
下面是我自己撸的一个散列表 逻辑思想基本跟hasnMap一样 里面有put方法get方法 和resize扩容方法
public class HashMapTest<K,V> {
private MapEntry[] table;
//存放大小
transient int size;
//扩容阀值
int threshold=8;
//扩容因子
float LOADFACTOR= 0.75f;
class MapEntry<K,V>{
K key;
V value;
MapEntry<K,V> next;
int hash;
public MapEntry(int hash,K key, V value,MapEntry<K,V> next) {
super();
this.hash=hash;
this.key = key;
this.value = value;
this.next=next;
}
}
public V put(K key,V value) {
if (table==null) {
table=new MapEntry[8];
}
if (key==null) {
return null;
}
int hash=hash(key);
int index=getIndex(hash,table.length);
for (MapEntry<K,V> e =table[index];e!=null;e=e.next) {
Object obj ;
if (e.hash==hash && ((obj=e.key)==key || obj.equals(key)) ) {
V oldValue=e.value;
e.value= value;
return oldValue;
}
}
addEntry(hash,key,value,index);
return null;
}
public V get(K key) {
if (key==null) {
return null;
}
MapEntry<K, V> entry= getEntry(key);
return entry==null ? null :entry.value;
}
private MapEntry<K, V> getEntry(K key) {
int hash=hash(key);
int index=getIndex(hash,table.length);
for (MapEntry<K,V> e =table[index];e!=null;e=e.next) {
Object obj ;
if (e.hash==hash && ((obj=e.key)==key || obj.equals(key) )) {
return e;
}
}
return null;
}
private void addEntry(int hash, K key, V value, int index) {
//1.先判断是否扩容
if (size >= threshold && table[index]!=null) {
System.out.println("kuo");
//扩容一倍
resize(size << 1);
index=getIndex(hash, table.length);
}
createEntry(hash,key,value,index);
}
private void resize(int newCapcity) {
MapEntry<K,V> [] newTable =new MapEntry[newCapcity];
transform(newTable);
table=newTable;
threshold= (int) (newCapcity * LOADFACTOR) ;
}
private void transform(MapEntry<K,V>[] newTable) {
int capcity=newTable.length;
for (MapEntry<K,V> e : table) {
while (null!=e) {
MapEntry<K,V> next = e.next;
int index = getIndex(e.hash,capcity);
e.next=newTable[index];
newTable[index]=e;
e=next;
}
}
}
private void createEntry(int hash, K key, V value, int index) {
MapEntry<K, V> entry=new MapEntry<>(hash, key, value, table[index]);
table[index]=entry;
size++;
}
private int getIndex(int hash,int length) {
//降低时间复杂度 更散
return hash & length -1;
}
private int hash(K key) {
int h = 0;
return (key==null) ? 0:(h=key.hashCode() ^ (h >>>16));
}
public int getTableSize() {
return table.length;
}
}
以上代码仅供参考 有不对的地方请批评指定
网友评论