2018年10月17日(星期三)  农历:戊戌年九月初九

作者:三年。分类: JAVA

概念

1、hash

翻译过来是哈希,还有种叫法散列,学过数据结构的应该知道。哈希就是将任意长度输入值通过哈希算法得到一个固定长度输出值。这里不重点介绍hash算法。

java 的hashmap实现

1、存储结构

首先我们知道 map中存的元素是Entry.

hashmap类使用一个Entry数组来实现存储,数组中每个元素可能对应一个链表

/**

* The table, resized as necessary. Length MUST Always be a power of two.

*/

transient Entry[] table;

构造函数,我们一般调用这个:

/**

* Constructs an empty <TT>HashMap</TT> with the default initial capacity

* (16) and the default load factor (0.75)。

*/

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR;

threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

table = new Entry[DEFAULT_INITIAL_CAPACITY];

init();

}

2、put方法,向hashmap中添加数据

/**

* Associates the specified value with the specified key in this map.

* If the map previously contained a mapping for the key, the old

* value is replaced.

*

* @param key key with which the specified value is to be associated

* @param value value to be associated with the specified key

* @return the previous value associated with <TT>key</TT>, or

*         <TT>null</TT> if there was no mapping for <TT>key</TT>.

*         (A <TT>null</TT> return can also indicate that the map

*         previously associated <TT>null</TT> with <TT>key</TT>.)

*/

public V put(K key, V value) {

if (key == null)

return putForNullKey(value);

int hash = hash(key.hashCode());

int i = indexFor(hash, table.length);

for (Entry<K,V> e = table[i]; e != null; e = e.next) {

Object k;

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

V oldValue = e.value;

e.value = value;

e.recordAccess(this);

return oldValue;

}

}

modCount++;

addEntry(hash, key, value, i);

return null;

}

我们看到先对key重新计算哈希值,然后根据该值找到数组小标,如果数组的这个位置有值,那么在这个位置上就以链表形式存储,新的值放在链表头。

/**

* Applies a supplemental hash function to a given hashCode, which

* defends against poor quality hash functions.  This is critical

* because HashMap uses power-of-two length hash tables, that

* otherwise encounter collisions for hashCodes that do not differ

* in lower bits. Note: Null keys always map to hash 0, thus index 0.

*/

static int hash(int h) {

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor)。

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

3、get 取方法

public V get(Object key) {

if (key == null)

return getForNullKey();

int hash = hash(key.hashCode());

for (Entry<K,V> e = table[indexFor(hash, table.length)];

e != null;

e = e.next) {

Object k;

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

return e.value;

}

return null;

}

先计算key的哈希值,然后找到数组中对应位置,让后通过for循环来遍历该位置上的链表,并用equals比较查找。

温馨提示如有转载或引用以上内容之必要,敬请将本文链接作为出处标注,谢谢合作!

已有 0/1112 人参与

发表评论:



手Q扫描加入Java初学者群