HashMap浅析

        HashMap浅析

在分析HashMap之前，我想先大致讲一下集合框架的几个接口及其分类。

在JAVA里面有一个类集的概念。所谓的类集就是一个动态的对象数组，最重要的是类集框架本身不受对象数组长度的限制。在整个JAVA类集中最常用的类集接口及他们的关系如下如所示：

 
             
 

 

 

       

                      

 

HashMap

1.HashMap的数据结构

    在知道HashMap是什么之前，我们先来看一下HashMap它的底层数据结构，如图所示，HashMap是一个数组和链表相结合，横向是一个数组，纵向是一个链表。

当我们先建一个HashMap的时候，就会初始化一个这样的数组。

 

 
 

 

 

在存放key—value键值对时，先将键值对封装成Entry对象，再把Entry这个对象存入数组中。一个Entry对象有四个属性：key，value，hash, next。而next类似于指针一样，指向下一个元素的引用。

当我们HashMap中存放（put）元素A时，先根据key的hash值得到A元素在数组中的下标位置，如果这个位置上没有其他元素，便可将A元素直接存入此位置；如果这个位置上已经存放了其他元素B，那么在此位置上的元素将以链表的形式存储，将新加入的元素A放在链头，最先加入的元素B放在链尾，即将A的属性next指向元素B。

同样的，从HashMap表中取出（get）某一个元素时，也要首先计算key的hash值得到此元素在数组中的存储位置，然后通过key的equals()方法在链表中找出相应的元素。写到这里我们知道，数组存储位置上，链表的长度越短，查询的速度越快，效率也就越高，所以怎么样让链表尽可能的长度短一点，这就需要有一个好的Hash函数了。

 

我们看到，在eclipse中，他的hash值是通过key的hashcode进行某种运算得到的；

代码如下：

 

int hash = hash(key.hashCode()); 
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4); 
}

 

   

在存放或获取时，获取的数组的下标位置由以下方法得到，

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

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

 

 

 

 

 

在存放某一个元素时，方法如下： 

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

 

 

 

        如此一来，HashMap底层的数据结构就大致缕清楚了，亲们，你懂了吗........

评论

1 楼 luliangy 2013-01-14  

学弟先把博客标题写对了撒~