偶然间翻到了自己之前在学校时,倒腾的HashMap源码,当初自己通过断点一点点的分析了jdk1.7中HashMap的一些逻辑,感觉1.7的源码还是比较简单清晰一点的,于是便记录了下来。
public class TestMap {
//默认为null
static final Entry[] empty_table={};
//用来存储实际数据
private Entry[] tables=empty_table;
//负载因数:用来计算阈值
private float loadFactor=0.75F;
//阈值:用来判断是否扩容的临界点
private int threshold=16;
//key-value数量
private int size;
//链表
static class Entry{
final Object key;
int hash;
Entry next;
Object value;
Entry(int h, Object k, Object v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
}
public TestMap(int threshold,float loadFactor) {
this.loadFactor = loadFactor;
this.threshold = threshold;
}
public TestMap() {
}
public Object put(Object key, Object value){
if(tables==empty_table){
init_table(threshold);//初始化table
}
if(key==null){//此处应返回Null对应的值,
throw new RuntimeException("返回NULL键对应的值");
}
int hash=key.hashCode();
int index=indexFor(hash,tables.length);
//查找链表中是否有重复的key
for(Entry e=tables[index] ; e!=null ; e=e.next){
if(hash==e.hash && (key==e.key)|| (null!=key && key.equals(e.key))){
//存在重复的Key (hash相同且key全等或equals相等)
Object oldValue=e.value;
e.value=value;
return oldValue;
}
}
addEntry(hash, key, value, index);
return null;
}
//初始化table
private void init_table(int threshold) {
//计算容量
int capacity=Integer.highestOneBit(((threshold-1) << 1)) ;
tables=new Entry[capacity];
this.threshold =(int)(capacity * loadFactor);//更新阈值
}
private void addEntry(int hash,Object key,Object value,int bucketIndex){
//键值对数量超过临界点,且bucketIndex处存在元素时,进行扩容
if(size>=threshold && null!=tables[bucketIndex]){
resize(2*tables.length);//对原数组进行扩容
//扩容过后需要再次计算bucketIndex及hash
hash=key.hashCode();
bucketIndex=indexFor(hash,tables.length);
}
createEntry(hash, key, value, bucketIndex);
}
private void resize(int size) {
Entry[] oldtables=tables;
int oldlength=tables.length;
Entry[] newtables=new Entry[size];
for (Entry old : oldtables) {//转移元素
while(old!=null){
Entry next=old.next;
int bucketIndex=indexFor(old.hash,newtables.length);//当前元素在新数组中的位置
old.next=newtables[bucketIndex];
newtables[bucketIndex]=old;
old=next;
}
}
//更新阈值
threshold=(int)(size*loadFactor);
tables=newtables;
}
void createEntry(int hash, Object key, Object value, int bucketIndex){
Entry e=tables[bucketIndex];//新添加的元素在链表头部
tables[bucketIndex] = new Entry(hash, key, value, e);
size++;
}
//通过键取值
public Object get(Object key){
if(key==null)
throw new RuntimeException("null Key");
//此处应返回NULL键对应的值,
Entry entry=getEntry(key);
return null==entry? null : entry.value;
}
private Entry getEntry(Object key) {
if(tables.length==0)
return null;
int hash= (key==null) ? 0: key.hashCode();
int index= indexFor(hash,tables.length); //通过hash及数组长度找到hash桶的位置
for(Entry e=tables[index] ; e!=null ; e=e.next){//遍历链表
if(e.hash == hash &&
( key == e.key ||( key != null && key.equals(e)))){
return e;
}
}
return null;
}
//通过hash及数组长度找到下标
static int indexFor(int h,int length){
return h & (length-1);
}
}
总结:
JDK1.7数据结构:数组/哈希表+链表
JDK1.8数据结构:数组/哈希表+链表+红黑树