jdk1.6源码学习---HashMap和HashTabel

       HashMap和HashTable两个是jdk.util包下2个经常使用的类，他们都继承AbstractMap抽象类，该抽象类实现了Map接口

     原理 ：hashMap和HashTable是根据key的hashcode来直接定位数组中的每个下标值，这样就不用进行for循环，然后因为不同的key会产生相同的hashcode，在同个table[i]下标下有多个。key-value这样的Entry，所以在Entry中又有一个next成员变量对这些Entry实现一个链表形式。如图：

 
     hashMap:首先HashMap的组成是一个数组加链表 的结构，也可以理解为数组里面的每个元素其实是一个链表，即a->b->c,通过a来获得b，b可以获得c，在hashMap中使用的key-value的模式，这种模式其实是封装在一个object当中，在这个object中有2个成员变量一个是key，一个是value。当然在hashMap中这个object的类真实名称是Entry在hashmap中的674行，在Entry中存放的有四个值：key value next hash //key即hashMap中的key，value即对应的值，next即链表中的下一个Entry对象，hash是每个key的hashcode(在内存中hashcode代表的是key是内存中存放的地址).   

     在hashMap中有三个构造函数，当然无非是几个之间相互调用而已：最主要的一个构造函数如下：

    //initialCapaity:传入的hashMap参数,loadFactor:对于hashMap的空间和时间效率因素
    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);
   
    //上面的语句都没什么用，废话，直接看下面
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;//这里其实是一个2的平方,所以当你创建一个hashmap以为方法的第一个参数为10,以为hashmap的数组长度就是10就错了，是16

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);//这个就是当一个hashMap中数据个数超过threshold的时候就会进行数据扩展（下面进行说明）
        table = new Entry[capacity];
        init();//jdk中保留
    }

 

   //下面介绍最重要的2个方法：其余的方法我想基本都不是什么问题了
    //首先是put方法：

    public V put(K key, V value) {
        if (key == null)//当key值为null的时候进行特定的放入数据:由此可见hashMap的key是可以为null的
            return putForNullKey(value);
        int hash = hash(key.hashCode());//获得key的hashcode
        int i = indexFor(hash, table.length);//这个是hashcode和数组长度进行与比较,这样可以使得i的值不操作数组长度并且跟hashcode是有直接相连的
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {//下面是数组中的一个table[i]确定的元素进行链表循环
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//当key值原来已经存在的时候进行值替换
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;//这个参数是hashmap中用来统计你对当前hashmap进行了多少次操作
        addEntry(hash, key, value, i);//这个方法是将key和value放入数组中
        return null;
    }

  //具体添加

   void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];//讲table[i]中的第一个Entry传给临时变量
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//table[i]中指向这个新创建的Entry，并将临时变量传递给next
        if (size++ >= threshold)//用来数组的扩容
            resize(2 * table.length);
    }

 

下面讲解下为什么使用threshold，默认是（数组长度/0.75）因为数组是链表形式所以数组是可以放无限个Entry(内存允许)，但对于查找效率将会随着链表的长度增加而降低，所以需要在Entry个数达到一定数量的时候进行数组的扩充。

    HashTable：HashTable的原理和HashMap的原理是一样（或者说基本都是一样）的，但是看源代码可以发现，hashTable中每个方法都添加一个同步机制synchronized，也就是

hashTable是线程安全的。还有一个区别就是hashtabel中key和value值都不允许为null，具体看hashtable的方法。

     备注：我想把我看到的和分析的写下来，对自己是非常有帮助的，希望看到的朋友如果觉得有什么不对的地方能指出来,Thanks !

评论

1 楼 287854442 2011-11-08  

写的很不错 顶了