java需要关注的知识点---HashMap

做了两年的java，感觉技术上没多大提升，特别是呆了一年外企，整理感觉自己都萎靡，不爱学习！
所以，写个帖子记下在网上看到的东西以及自己要去学习的内容！
努力奋斗！
1.HashMap的实现--------------------<在看>
   1.1 HashMap 的默认size是16，默认临界值是 12，默认的基数0.75。
   1.2 HashMap 的最大size是1<<30
   1.3 HashMap 中 transfer方法理解：

        

   
        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];//标记1
            if (e != null) {
                src[j] = null;//标记2
                do {
                    Entry<K,V> next = e.next;//标记3
                    int i = indexFor(e.hash, newCapacity);//标记4
                    e.next = newTable[i];//标记5
                    newTable[i] = e;//标记6
                    e = next;//标记7
                } while (e != null);
            }
        }
    }

    标记1：从Entry 数组中获取到 oldTable中需要往newTable 插入的entry实例e。
    标记2：回收oldTable的内存。
    标记3：使用临时变量存储e.next的值，以便下次获取链表的下个需要遍历的值，直到e.next的值为空。
    标记4：根据e的hash值和新表中的容量计算e需要放置在新数组中的index值。
    标记5：把新数组index位置的值传递给e.next.
    标记6：把e放置在新数组index的位置下。
    标记7：重新设置e的值，把老数组e的next值传递给e.继续下一轮循环，直到e的next为空。


   1.4 HashMap 中 put 方法：

  

 public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        //根据hash算法获取需要插入数据的hash值
        int hash = hash(key.hashCode());
        //根据hash值，计算将要插入数组的index值
        int i = indexFor(hash, table.length);
        //如果该index下，存在链表值，遍历该链表，对比
        //链表中的每一个entry的实例的hash值和key
        //是否和需要插入的key和key的hash值相同。
        //如果相同：跟新原entry下的value;保持key，index和hash值不
        //变。
        //如果不相同：把新纪录插入到数组中。
        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;
    }
   

   1.5 HashMap中的addEntry方法:

   void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        //如果数组table的长度大于临界值，将table进行扩容，长度为原来的
        //两倍。
        if (size++ >= threshold)
            resize(2 * table.length);
    }

    1.6 HashMap中的静态内部类Entry：

 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * h:新创建的entry实例的hash值。
         * k:键值
         * v:值
         * n:链表中但前entry实例的下一个entry的值。
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
	    V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

  
        void recordAccess(HashMap<K,V> m) {
        }

        void recordRemoval(HashMap<K,V> m) {
        }
    }

    1.7 HashMap中的remove()方法：

final Entry<K,V> removeEntryForKey(Object key) {
        //获取hash值，如果key是null，hash值为0.
        int hash = (key == null) ? 0 : hash(key.hashCode());
        //获取该key的下标值。
        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;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                  //移动数组,用需要删除数组后一位置的值覆盖当前位置
                    table[i] = next;
                else      
                 //把需要删除的值，用当前链表中的下一个值
                //进行覆盖，依次用下一个覆盖上一个，直到
                //需要删除纪录后的每一数据都向前移动一位。
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

有代码可得知：hashmap的删除不知是单单的把需要删除的纪录内存释放（设置为null）。而是
移动需要删除纪录后的每一个元素来覆盖前元素，释放最后一个值。
    1.8 HashMap 中的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为空的时候，hashmap从table[0]的位置获取专门存取null键的位置获取值，key不为空的时候，根据传入key的hash值，获取index值（数组下标），然后 遍历该index下的entry链表，比对该hash值下所有的key，如果有key和传入的key相同，
获取该key下的value.
    1.9 HashMap的结构图(见附件)
[img]

 [/img]

 

评论

1 楼 xiaguangme 2012-12-28  

写的很不错