哈希、HashMap原理及源码、Hash的一些应用面试题

    6、HashMap不是线程安全的，多线程环境下可以使用Hashtable或ConcurrentHashMap。

    7、我们能否让HashMap同步？
         HashMap可以通过下面的语句进行同步：
         Map m = Collections.synchronizeMap(hashMap);

    图1：

    图2：

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);// HashMap接收key为null的数据
        int hash = hash(key);//对key的hashCode再进行hash运算
        int i = indexFor(hash, table.length);//根据hash值和entry数组的大小计算出新增数据应该存放的数组位置
        for (Entry e = table[i]; e != null; e = e.next) {
            // for循环遍历找到的数组下标的entry，如果hash值和key都相等，则覆盖原来的value值       
            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++;
        //如果上面for循环没有找到相同的hash和key，则增加一个entry
        addEntry(hash, key, value, i);
        return null;
    }
	
	void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length); //如果size超过threshold，则扩充table大小。再散列
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }
    
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry e = table[bucketIndex];
        //new 一个新的entry，赋值给当前下标数组
        table[bucketIndex] = new Entry<>(hash, key, value, e); //参数e, 是Entry.next
        size++;
    }
    
    Entry(int h, K k, V v, Entry n) {
            value = v;
            //在HashMap的Entry中有四个变量，key、value、hash、next，其中next用于在hash方法添加值冲突时候，所指向的下一个值。
            next = n;//即将原来数组下标对应的entry赋值给新的entry的next
            key = k;
            hash = h;
        }

       PS: HashMap，也是先判断hashcode（hashcode相同，所以它们的table位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。），再判断equals，如果都相同，则表示：在集合添加中，认为是同一个"东西"，覆盖旧值。【==、equals、hashcode的区别和联系】

public V get(Object key) {
        if (key == null)//key为null时特别处理
            return getForNullKey();
        Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
    
    final Entry getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        //indexFor(hash, table.length) 根据hash值和数组长度计算出下标，然后遍历Entry链表
        for (Entry 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;
    }

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

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
	
	void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry e : table) {
            while(null != e) {
                Entry next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

http://blog.csdn.net/paincupid/article/details/47699735