HashMap源码解读

Hash结构，简单的说，就是一个数组+链表，数组里面存了一个个链表。

 

Java里面的关于Hash的类有三个：HashMap/HashSet/HashTable

 

其中，HashMap继承了抽象类AbstarctMap，实现了接口Map<K,V>, Cloneable, Serializable。百度百科上说：

HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）

 

1、定义的一些变量和常量

 

 

 

static final int DEFAULT_INITIAL_CAPACITY = 16;

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

transient Entry[] table;

transient int size; 

int threshold;

final float loadFactor;

transient volatile int modCount;

 

 其中，DEFAULT_INITIAL_CAPACITY为默认的初始容量，默认的初始容量必须是2的幂。MAXIMUM_CAPACITY是最大容量，需小于2的30次方。DEFAULT_LOAD_FACTOR为默认加载因子，为0.75。

 

 

 

Entry[]是一个实现了Map.Entry接口的类，其实就是HashMap最主要的部分，整个数据就是存在这个Entry[]里面的。他的结构里定义了

 

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

 

 其实就是一个数组里存了链表的结构，这应该算是HashMap的核心部分。

 

 

剩下的是一些未赋值的变量。size是HashMap的大小，源码的注释是The number of key-value mappings contained in this map.意思是图中的Key值的映射数。threshold=(capacity * load factor)，是HashMap的实际容量。loadFactor是用于哈希表的负载因子。modCount，注释里写的是hashMap被修改的次数（HashMap的映射数的改变或修改它的内部结构，如rehash）。

 

 

 

2、构造函数

 

 

 

HashMap的构造函数有四个，其中的

 

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

 

 全是默认值，就是先前定义里的常量。还有可以自己定义容量以及负载因子的，如

 

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }

 

 

 

3、函数

 

 

 

1.初始化函数   void init() ;

 

2. static int hash(int h)  不知道什么意思，百度了下，据说是随机获得一个h的值;

 

3.static int indexFor(int h, int length)             返回元素索引的方法;

 

4.public int size()           返回大小;

 

5.public boolean isEmpty()            判断是否为空;

 

6.下面是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值为空，则返回getForNullKey();这也是一个函数，下面会讲到。如果key不为空，则根据key 的hash值找到相应的元素，若没有找到相应的元素，则返回null。

 

7.private V getForNullKey()     返回key值为null的value值

 

8.public boolean containsKey(Object key)            HashMap中是否已经存在key值

 

9. final Entry<K,V> getEntry(Object key)                  返回key键在HashMap里的条目（数组中链表的一个结点）。如果在HashMap中没有则返回null。

 

 10.public V put(K key, V value)           将一个value和对应的key放入HashMap中

 

11. private V putForNullKey(V value)         将 key为null对应的值改成value 

 

……突然发现方法太多了。。写都写不完，我就挑一些写。。

 

public V remove(Object key)            删除一个KEY值

 

还有一个很重要的函数

 

 

 void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

 

 

 

这是把旧表rehash成一个新表。在建立的hash结构太不均匀的时候，我们需要rehash，rehash实质上就是扩容过程，就是把原先的数组变成更大的数组。其实rehash是一个很耗费时间的过程，所以在建立hash函数的时候就要注意，要符合实际情况。否则rehash会浪费很大的时间和空间。

 

 

 

评论

1 楼 再_见孙悟空 2013-12-21  

写的很好喔