Java7 hashmap

丹

发布于 2019-05-06 17:47:22

6330

发布于 2019-05-06 17:47:22

文章被收录于专栏：WD学习记录WD学习记录

JDK1.7中的hashmap。

HashMap继承自AbstractMap，实现了Map、Cloneable、Serializable接口。

默认初始容量为：1<<4 即 16

最大容量为：1<<30 即2的30次方

默认负载因子：0.75

Entry<K,V>数组。

每个Entry的属性：

final K key;
V value;
Entry<K,V> next;
int hash;

hashmap put方法

public V put(K key, V value){
    if(table == EMPTY_TABLE){
        inflateTable(thresold);
    }
    if(key==null){
        return putForNullKey(value);
    }
    int hash=hash(key);
    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;
}

put方法流程：

（1）如果table为空，进行初始化。

（2）如果keyt为null，调用putForNullKey()方法

（3）获取key的hash

（4）根据hash值获取当前节点所在的index，使用的方式是i=hash&(table.length-1)；

（5）如果table[i]的位置不为null，对链表进行遍历，找到hash和key值都相等的节点，然后覆盖原来的value，并返回旧的value；

（6）如果对应位置为null，或者通过遍历找不到该节点，则modCount++并调用addEntry（）。

addEntry()方法

void addEntry(int hash, K key, V value, int bucketIndex){
    if((size>=threshold)&&(null!=table[bucketIndex])){
        resize(2*table.length);
        hash=(null!=key)?hash(key):0;
        bucketIndex=indexFor(hash,table.length);
    }
    createEntry(hash,key,value,bucketIndex);
}

如果size已经超过了threshold并且对应位置不为空，resizehashmap。然后重新计算hash和桶位置。并创建新的entry。在创建新节点之后，将size++；

hashmap get方法

key为空，调用getForNullKey。不为空，调用getEntry。通过key计算对应的桶位置，并遍历该位置的链表获取节点。、

hashmap resize()方法

void resize(int newCapacity){
    Entry[] oldTable=table;
    int oldCapacity=oldTable.length;
    if(oldCapacity==MAXIMUM_CAPACITY){
        threshold=Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable=new Entry[newCapacity];
    transfer(newTable,initHashSeedAsNeeded(newCapacity));
    table=newTable;
    threshold=(int)Math.min(newCapacity*loadFactor,MAXIMUM_CAPACITY+1);
}

transfer方法

void transfer(Entry[] newTable, boolean rehash){
    int newCapacity=newTable.length;
    for(Entry<K,V> e: table){
        while(null!=e){
            Entry<K,V> next=e.next;
            if(rehash){
                e.hash=null==e.key?0：hash(key);
            }
            int i=indexFor(e.hash,newCapacity);
            e.next=newTable[i];
            newTable[i]=e;
            e=next;
     }
}

resize方法流程：

新建一个长度为原来两倍的数组，将原数组中的内容rehash到新的数组中，然后指向新的table。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年04月21日，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap