HashMap源码分析

     

[size=medium;]HashMap源码分析[/size]

 

    HashMap用来存储key-value对，内部使用拉链法Hash表作为存储结构，key-value被封装成Entry<K, V>，Entry也是链表结点。

 

   1. Hash表的内部结构如下：

 

 <span style="white-space: pre;">   Entry<K, V> table[];</span>

 

    table[0]-->Entry(K,V)-->Entry(K,V)
    table[1]-->Entry(K,V)
    table[2]
    table[3]-->Entry(K,V)
    table[.]

 

    Entry<K,V>数据域代码:

 

    <span style="white-space: pre;">static class Entry<K,V> implements Map.Entry<K,V> {</span>

	        final K key;
	        V value;
	        final int hash;
	       [b] Entry<K,V> next;[/b]
}

 
 

 

    HashMap的Key-Value对，被包装成Entry(K,V)，根据key计算hash值，确定在table数组的下标位置，数组元素为链表的链表头，被计算hash映射到相同数组下标位置的key-value都被存储在这个链表当中，这就是解决hash冲突的办法 。

 

   2.HashMap中查找目标Entry<K,V>

 

    也就是说根据key进行hash只能找到Entry(K,V)在哪个链表当中，查找到具体确切的Entry(K,V)还需要遍历整个链表的每个节点，针对每个节点去匹配key值，如果链表很长，那么效率就会很低，体现不出Hash表的优势。理想的情况是每个链表不多于一个节点，这样通过hash就可以直接找到目标Entry(K,V)，能够在O(1)内实现元素的查找，像数组一样，在存储内容与存储位置之间建立直接的映射关系。

 

 

    3.HashMap中的扩容

 

    为了提升Hash表的性能，在HashMap中存储的k-v对数目超过了预定的负载量threshold时，就对HashMap进行扩容，实际上就是使用table[]数组成倍增加，这样做的目的是使每个链表长度较为短小，能够实现快速的定位目标结点；但是扩容需要对原HashMap中的每个结点重新计算存储位置，迁移到新的table[]当中，这也是一笔不少的开销，应该减少扩容的次数，所以根据应用场景选择一个合适的loadFactor和capacity比较重要,loadFactor和capacity可以在HashMap的构造函数中设置。

 

    Threshold计算: threshold = (int)(capacity * loadFactor);( 当前容量 * 负载因子)


<p style="margin: 0px;">    Static int final DEFAULT_INITIAL_CAPACITY = 16;

<p style="margin: 0px;"> 

<p style="margin: 0px;">    4.HashMap不是线程安全的，代码中没有任何的同步措施，在多线程中环境中需要注意。

<p style="margin: 0px;"> 

<p style="margin: 0px;">    5.代码分析

<p style="margin: 0px;">       构造函数

<p style="margin: 0px;"> 

<p style="margin: 0px;"> 

//指定初始容量和负载因子的构造函数  
 public HashMap(int initialCapacity, float loadFactor) {
	    	
	    	//检测参数的合法性initialCapacity, 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;
	        
	        //当HashMap存储的键值对数，超过threshold，就需要对整个hash table进行扩展
	        //threshold = capactiy * loadFactor;通过负载因子计算得来.
	      
	        threshold = (int)(capacity * loadFactor);
	        
	        //为HashMap依赖的table申请空间
	        table = new Entry[capacity];
	        init();
	    }

 

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

 
    <span style="white-space: pre;">    public HashMap(int initialCapacity) {</span>

	        this(initialCapacity, DEFAULT_LOAD_FACTOR);
	    }

 

 

    get(k)方法

 

    
	    public V get(Object key) {
	    	
	    	//如果key是null,返回一个Object对象作内部处理，HashMap中可以使用null作为key
	        Object k = maskNull(key);
	        
	        //计算此k(key)对应的hash值
	        int hash = hash(k);
	        
	        //indexFor:h & (length-1)
	        //计算此key在hash表中的映射到的数组元素位置(每个元素是一个指向链表的头结点)
	        int i = indexFor(hash, table.length);
	        
	        //取得链表头，映射到数组同一位置的元素被组织成一个链表(冲突解决方法)
	        Entry<K,V> e = table[i]; 
	        
	        while (true) {
	        	
	        	//如果查找到链表末尾，表示没有查找到，返回null
	            if (e == null)
	                return null;
	            
	            //判断所以给key,与存储在HashTable中key是否完全相等
	            //如果完全相等，则查找到目标key-value对，返回value object
	            //x与y两个key完全相等的条件:x == y || x.equals(y);
	            //也就是说如果两个key内容相等或者指向同一个对象引用，均算作相等。
	            if (e.hash == hash &amp;&amp; eq(k, e.key)) 
	                return e.value;
	            
	            //继续查找下一个元素
	            e = e.next;
	        }
	    }

 

 

 

    put(k,V)

 

    <span style="white-space: pre;"> public V put(K key, V value) {</span>

	    	
	    	//如果key为null，通过maskNull转换成Object对象进行内部存储操作
	    	K k = maskNull(key);
	    	
	    	//计算key对应的hash值，确定在Hash数组中的位置
	        int hash = hash(k);
	        int i = indexFor(hash, table.length);

	        
	        //找到链表的头结点后，首先在链表中确定此key是否被其它的key-value对所占用
	        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
	        	
	        	[b]//如果此key已经在HashMap中存在，则更新此key-value中的value值[/b]
	            if (e.hash == hash &amp;&amp; eq(k, e.key)) {
	                V oldValue = e.value;
	                e.value = value;
	                e.recordAccess(this);
	                
	                //并且返回oldValue
	                return oldValue;
	            }
	        }

	        modCount++;
	        //确定此key不存在HashMap中后，直接将key-value存入HashMap中，也就是插入链表中
	        [b]addEntry(hash, k, value, i);[/b]
	        return null;
	    }



void addEntry(int hash, K key, V value, int bucketIndex) {
	    	
		    Entry<K,V> e = table[bucketIndex];
		    //Entry内部用来封装key-value对
	        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
	        /[b]/如果当前HashMap中存储的k-v对数目(size)超过threshold，需要对整个HashMap进行扩容
	        //扩展成原来的2倍大小[/b]
	        if (size++ >= threshold)
	            resize(2 * table.length);
	    }


void resize(int newCapacity) {
	        Entry[] oldTable = table;
	        int oldCapacity = oldTable.length;
	        if (oldCapacity == MAXIMUM_CAPACITY) {
	            threshold = Integer.MAX_VALUE;
	            return;
	        }
            
	        //为HashMap分配新的内存空间
	        Entry[] newTable = new Entry[newCapacity];
	        
	        //迁移旧HashMap上的数据到新的空间newTable上
	        transfer(newTable);
	        
	        table = newTable;
	        
	        //重新计算负载上限
	        threshold = (int)(newCapacity * loadFactor);
	    }


    	    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;
	                
	                //为链表中的每一个结点重新分配新的位置在newTable当中
	                //因为位置的计算是hash &amp; (length-1);length改变了，所以存储位置也跟着变了
	                
	                do {
	                	
	                    Entry<K,V> next = e.next;
	                    
	                    //计算结点e的新的存储位置在newTable中
	                    int i = indexFor(e.hash, newCapacity);
	                    
	                    //将结点添加到链表newTable[i]中
	                    e.next = newTable[i];
	                    newTable[i] = e;
	                    
	                    //e指向下一个结点
	                    e = next;
	                } while (e != null);
	                
	            }
	        }
	    }

 
    remove(k)方法

 

   <span style="white-space: pre;"> public V remove(Object key) {</span>

	        Entry<K,V> e = removeEntryForKey(key);
	        return (e == null ? null : e.value);
 }



Entry<K,V> removeEntryForKey(Object key) {
	    	
	    	//根据key计算hash值，映射到数组下标位置，找到链表头
	        Object k = maskNull(key);
	        int hash = hash(k);
	        int i = indexFor(hash, table.length);
	        
	        Entry<K,V> prev = table[i];
	        Entry<K,V> e = prev;

	        while (e != null) {
	        	
	            Entry<K,V> next = e.next;
	            
	            //查找封装目标key-value的Entry
	            if (e.hash == hash &amp;&amp; eq(k, e.key)) {
	                modCount++;
	                size--;
	                
	                [b]//这种情况只有在链表中只有一个结点时候才会才成立[/b]
	                if (prev == e) 
	                    table[i] = next;
	                
	                else
	                    prev.next = next;
	                e.recordRemoval(this);
	                return e;
	            }
	            //在遍历过程中记录当前结点e的前驱
	            prev = e;
	            e = next;
	        }
	   
	        return e;
	    }

 
   eq()用于比较两个key是否相等

   两个key相等的条件是:(1).两者指向同一个引用

                                  (2).两者equals相等(考虑是否要重写key类的equals()，根据需要)

 

   <span style="white-space: pre;">  static boolean eq(Object x, Object y) {</span>

	        return x == y || x.equals(y);

  }

 
 

 

 

 

 

评论

1 楼 liuyes 2012-02-08  

写的有点乱呀