posts - 28,  comments - 15,  trackbacks - 0
    HashMap内部有一个Entry数组,可以称之为hash table。HashMap的默认构造值为初始容量为16,负载因子为0.75,阀值(初始容量*负载因子)为12。其默认构造子如下:
public class HashMap<K,V>
    
extends AbstractMap<K,V>
    
implements Map<K,V>, Cloneable, Serializable
{

    
/**
     * The default initial capacity - MUST be a power of two.
     
*/

    
static final int DEFAULT_INITIAL_CAPACITY = 16;

    
/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     * 
     * 如果一个较大的值被任意一个带有参数的构造器指定,最大容量被使用。
     
*/

    
static final int MAXIMUM_CAPACITY = 1 << 30;   //1073741824

    
/**
     * The load factor used when none specified in constructor.
     
*/

    
static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

    
transient Entry[] table;

    
/**
     * The number of key-value mappings contained in this map.
     
*/

    
transient int size;

    
/**
     * The next size value at which to resize (capacity * load factor).
     * 
     * 下一个用来调整的大小值
     * 
@serial
     
*/

    
int threshold;

    
/**
     * The load factor for the hash table.
     *
     * 
@serial
     
*/

    
final float loadFactor;

public HashMap() {
        
this.loadFactor = DEFAULT_LOAD_FACTOR;  
        threshold 
= (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table 
= new Entry[DEFAULT_INITIAL_CAPACITY];  //默认情况下,以容量为16构建Entry数组
        init();
    }


put方法分析:
 <1>HashMap首先判断key是否为null,如果为null,
    <1.1>HashMap从hash table中第0个位置的Entry,如果该Entry不等于null且entry.key也不为null,当前value覆盖entry的value。
    <1.2>否则,在hash table[0]处创建新的key=null的Entry。
 <2>
    接下来,以key的hashcode做hash运算,获得hash值。该hash值与hash table的长度-1做与操作,获得key在当前hash table中的位置索引。
    然后检查在该索引位置是否存在Entry对象,如果存在,且该Entry对象的key的hash值与上面计算的hash值相等,且entry的key与传入的key相等或者key.equals(entry.key),那么以当前的value值覆盖旧值,并返回旧值。
    如果hash table中不存在key所指定的Entry,那么就要增加新的Entry。在增加Entry后,要检查容量是否已经达到阀值,如果达到阀值,就以当前hash table的长度的2倍扩展。同时要重新计算entry在新的hash table中的索引位置。注意,由于hash计算可能导致key的hash值可能是重复的,HashMap采用链表的方式解决hash值冲突的问题,另外一种解决方法是开放地址法。
    以下是put方法部分代码:
public V put(K key, V value) {
        
if (key == null)
            
return putForNullKey(value);
        
        
/*这里对key的hasCode做hash*/
        
int hash = hash(key.hashCode());
        
/*通过hash值与hash表的长度减1做与操作获取hash表的索引值*/
        
int i = indexFor(hash, table.length);
        
/*由于hash可能重复,导致获取重复的索引值,这里通过判断传入的key的has值与当前节点的key的has值是否相等,且key相等或者equals相等,来用新的value替换旧值,并返回旧值*/
        
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为空的情况:

 private V putForNullKey(V value) {
        
/*从0桶查找key为null的Entry。如果桶中有null的Entry,那么把当前新的值设置到Entry中,并返回旧值*/
        
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            
if (e.key == null{
                V oldValue 
= e.value;
                e.value 
= value;
                e.recordAccess(
this);
                
return oldValue;
            }

        }

        
        modCount
++;
        addEntry(
0null, value, 0);
        
return null;
    }

计算key的hash值与计算key所应处在hash table中的位置:

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);
    }


    
/**
     * Returns index for hash code h.
     
*/

    
static int indexFor(int h, int length) {
        
return h & (length-1);
    }

增加entry节点以及扩容:

 void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry
<K,V> e = table[bucketIndex];//临时存储指定桶索引的Entry
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//在指定桶索引位置创建新的Entry,并自动把原桶索引的Entry作为当前Entry的next
        /*当size达到阀值(当前容量*负载因子=threshold),需要扩容*/
        
if (size++ >= threshold)
            resize(
2 * table.length);
    }

------------------------------------------------

 void resize(int newCapacity) {
        Entry[] oldTable 
= table;
        
int oldCapacity = oldTable.length;
        
/*如果就有容量达到默认的的容量最大值(2的30次方),threshold设为整形的最大值(2的31次方-1)*/
        
if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold 
= Integer.MAX_VALUE;
            
return;
        }


        Entry[] newTable 
= new Entry[newCapacity];
        
/*这里把源hash表中的数据拷贝到新的hash表中,注意的是,源hash表中链表到新hash表中由头变成了尾*/
        transfer(newTable);
        table 
= newTable;
        
/*设置扩容后新的阀值*/
        threshold 
= (int)(newCapacity * loadFactor);
    }


get方法分析:
    当调用get方法时,HashMap首先判断key是否为null,如果为null,其hash值为0,否则通过hash算法计算。
    接下来,通过该hash值与hash table的长度-1做与操作,获得key在hash table中的索引。如果entry不等null,且该传入key的hash值与entry的hash值相等,且key==entry.key或者key.equals(entry.key),则返回该entry.value.否则返回null.

    final Entry<K,V> getEntry(Object key) {
        
int hash = (key == null? 0 : 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 != null && key.equals(k))))
                
return e;
        }

        
return null;
    }







 


 

 

 

 

 

 

 

 

 

 

 

posted on 2012-02-13 14:42 zhangxl 阅读(411) 评论(0)  编辑  收藏 所属分类: JDK

只有注册用户登录后才能发表评论。


网站导航:
 
<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

常用链接

留言簿(1)

随笔分类(17)

随笔档案(28)

文章分类(30)

文章档案(30)

相册

收藏夹(2)

hibernate

java基础

mysql

xml

关注

压力测试

算法

最新随笔

搜索

  •  

积分与排名

  • 积分 - 95496
  • 排名 - 602

最新评论

阅读排行榜

评论排行榜