hashmap的底层实现

来源:转载

HashMap的底层实现都是数组+链表结构实现的,添加、删除、获取元素都是先计算hash值,根据hash值和table.length计算出index也就是table的数组的下标,然后进行相应的操作。

不过HashMap和HashTable计算hash的方法不同:

HashMap是直接用key的hashcode对table数组长度取模;而HashMap则是对key的hashcode进行两次hash,以获得更好的散列值,然后再对table数组的长度取模。

 

具体方法的实现:

HashMap默认初始化时会创建一个容量为16的Entry数组,默认加载因子为0.75,同时设置临界值16*0.75;

 public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR;

threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

table = new Entry[DEFAULT_INITIAL_CAPACITY];

init();

}

对于put方法:

HashMap会对null值key进行特殊处理,总是放到table[0]位置


put过程是先计算hash然后通过hash与table.length取摸计算index值,然后将key放到table[index]位置,当table[index]已存在其它元素时,会在table[index]位置形成一个链表,将新添加的元素放在table[index],原来的元素通过Entry的next进行链接,这样以链表形式解决hash冲突问题,当元素数量达到临界值(capactiy*factor)时,则进行扩容,是table数组长度变为table.length*2;

对于get方法:

同样当key为null时会进行特殊处理,在table[0]的链表上查找key为null的元素


get的过程是先计算hash然后通过hash与table.length取摸计算index值,然后遍历table[index]上的链表,直到找到key,然后返回

对于remove方法:

remove方法和put get类似,计算hash,计算index,然后遍历查找,将找到的元素从table[index]链表移除

对于resize方法:

resize方法在hashmap中并没有公开,这个方法实现了非常重要的hashmap扩容,具体过程为:先创建一个容量为table.length*2的新table,修改临界值,然后把table里面元素计算hash值并使用hash与table.length*2重新计算index放入到新的table里面,这里需要注意下是用每个元素的hash全部重新计算index,而不是简单的把原table对应index位置元素简单的移动到新table对应位置

对于containsKey方法:

containsKey方法是先计算hash然后使用hash和table.length取摸得到index值,遍历table[index]元素查找是否包含key相同的值

 

 

简单的MyHashMap:

public class MyHashMap {

//默认初始化大小 16

private static final int DEFAULT_INITIAL_CAPACITY = 16;

//默认负载因子 0.75

private static final float DEFAULT_LOAD_FACTOR = 0.75f;

//临界值

private int threshold;

//元素个数

private int size;

//扩容次数

private int resize;

private HashEntry[] table;

public MyHashMap() {

table = new HashEntry[DEFAULT_INITIAL_CAPACITY];

threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

size = 0;

}

private int index(Object key) {

//根据key的hashcode和table长度取模计算key在table中的位置

return key.hashCode() % table.length;

}

public void put(Object key, Object value) {

//key为null时需要特殊处理,为简化实现忽略null值

if (key == null) return;

int index = index(key);

//遍历index位置的entry,若找到重复key则更新对应entry的值,然后返回

HashEntry entry = table[index];

while (entry != null) {

if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {

entry.setValue(value);

return;

}

entry = entry.getNext();

}

//若index位置没有entry或者未找到重复的key,则将新key添加到table的index位置

add(index, key, value);

}

private void add(int index, Object key, Object value) {

//将新的entry放到table的index位置第一个,若原来有值则以链表形式存放

HashEntry entry = new HashEntry(key, value, table[index]);

table[index] = entry;

//判断size是否达到临界值,若已达到则进行扩容,将table的capacicy翻倍

if (size++ >= threshold) {

resize(table.length * 2);

}

}

private void resize(int capacity) {

if (capacity <= table.length) return;

HashEntry[] newTable = new HashEntry[capacity];

//遍历原table,将每个entry都重新计算hash放入newTable中

for (int i = 0; i < table.length; i++) {

HashEntry old = table[i];

while (old != null) {

HashEntry next = old.getNext();

int index = index(old.getKey());

old.setNext(newTable[index]);

newTable[index] = old;

old = next;

}

}

//用newTable替table

table = newTable;

//修改临界值

threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);

resize++;

}

public Object get(Object key) {

//这里简化处理,忽略null值

if (key == null) return null;

HashEntry entry = getEntry(key);

return entry == null ? null : entry.getValue();

}

public HashEntry getEntry(Object key) {

HashEntry entry = table[index(key)];

while (entry != null) {

if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {

return entry;

}

entry = entry.getNext();

}

return null;

}

public void remove(Object key) {

if (key == null) return;

int index = index(key);

HashEntry pre = null;

HashEntry entry = table[index];

while (entry != null) {

if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {

if (pre == null) table[index] = entry.getNext();

else pre.setNext(entry.getNext());

//如果成功找到并删除,修改size

size--;

return;

}

pre = entry;

entry = entry.getNext();

}

}

public boolean containsKey(Object key) {

if (key == null) return false;

return getEntry(key) != null;

}

public int size() {

return this.size;

}

public void clear() {

for (int i = 0; i < table.length; i++) {

table[i] = null;

}

this.size = 0;

}

@Override

public String toString() {

StringBuilder sb = new StringBuilder();

sb.append(String.format("size:%s capacity:%s resize:%s\n\n", size, table.length, resize));

for (HashEntry entry : table) {

while (entry != null) {

sb.append(entry.getKey() + ":" + entry.getValue() + "\n");

entry = entry.getNext();

}

}

return sb.toString();

}

}

class HashEntry {

private final Object key;

private Object value;

private HashEntry next;

public HashEntry(Object key, Object value, HashEntry next) {

this.key = key;

this.value = value;

this.next = next;

}

public Object getKey() {

return key;

}

public Object getValue() {

return value;

}

public void setValue(Object value) {

this.value = value;

}

public HashEntry getNext() {

return next;

}

public void setNext(HashEntry next) {

this.next = next;

}

}

分享给朋友:
您可能感兴趣的文章:
随机阅读: