HashMap源码理解

看看HashMap对应的源码。

1.类、接口关系

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

克隆和序列化不懂，先看Map。

2.实现的接口 Map

public interface Map<K,V> {
     //这些方法就不用写注释了吧，一看就懂。
     int size();
     boolean isEmpty();
     boolean containsKey(Object key);
     boolean containsValue(Object value);
     V get(Object key);
     V put(K key, V value);
     V remove(Object key);
     void putAll(Map<? extends K, ? extends V> m);
     void clear();
     //这里是返回的不重复的集合
     Set<K> keySet();
     //这里返回的是一个集合
     Collection<V> values();
     Set<Map.Entry<K, V>> entrySet();
     boolean equals(Object o);
     int hashCode();
     //还有一个内部的接口，这个相当于一个key-value数据。
     interface Entry<K,V> {
     	K getKey();
        V getValue();
	V setValue(V value);
        boolean equals(Object o);
	int hashCode();
    }
}

3.继承的抽象类AbstractMap

这个方法有700行，我就挑出几个说一说

3.1构造方法

public abstract class AbstractMap<K,V> implements Map<K,V> {
    protected AbstractMap() {
    }
}

3.2 几个方法

简单介绍几个，都没什么实际意思。

//声明了抽象变量，里面直接是Map的内部类，这个Set包含着所有的数据key+value
public abstract Set<Entry<K,V>> entrySet();

//Map长度
public int size() {
      return entrySet().size();
}

//是否为空
public boolean isEmpty() {
	return size() == 0;
}

//是否包含某个值
public boolean containsValue(Object value) {
        //要查找出是否包含，于是开始遍历这个Set。
        //这里可以使用 for each，但是这个方法写于jdk1.2，所以当时还没有。遍历的过程很简单。
	Iterator<Entry<K,V>> i = entrySet().iterator();
        //这里还有一个判空。
	if (value==null) {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (e.getValue()==null)
		    return true;
	    }
	} else {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
                //注意：比较用的是equals，而不是==
		if (value.equals(e.getValue()))
		    return true;
	    }
	}
	return false;
}

//查找这个值，一样遍历Set
public V get(Object key) {
	Iterator<Entry<K,V>> i = entrySet().iterator();
	if (key==null) {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (e.getKey()==null)
		    return e.getValue();
	    }
	} else {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (key.equals(e.getKey()))
		    return e.getValue();
	    }
	}
	return null;
}

//这个方法是要求重写的。
public V put(K key, V value) {
	throw new UnsupportedOperationException();
}

//删除某个键值对
public V remove(Object key) {
	Iterator<Entry<K,V>> i = entrySet().iterator();
	Entry<K,V> correctEntry = null;
        //key值可以为null，查出相应key值所对应的键值对。
	if (key==null) {
	    while (correctEntry==null && i.hasNext()) {
		Entry<K,V> e = i.next();
		if (e.getKey()==null)
		    correctEntry = e;
	    }
	} else {
	    while (correctEntry==null && i.hasNext()) {
		Entry<K,V> e = i.next();
		if (key.equals(e.getKey()))
		    correctEntry = e;
	    }
	}
        //这里开始删除操作
	V oldValue = null;
	if (correctEntry !=null) {
	    oldValue = correctEntry.getValue();
            //用迭代器的删除方法。
	    i.remove();
	}
        //返回删除的value。
	return oldValue;
}

//添加一个Map操作，直接循环添加
public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
}

//直接使用了set的clear方法
public void clear() {
	entrySet().clear();
}

AbstractMap就看到这里，毕竟主要是看HashMap。

4.HashMap

4.0文字介绍

HashMap首先会开辟一个16空间的Entry（键值对）数组，

Entry类中包括

final K key;
V value;
Entry<K,V> next;
final int hash;

 

然后对存入的key进行hash运算，算到一个数字（1-15），存入对应位置。

如果对应位置一有数据，则替代当前数据，然后将原数据的引用给新数据，即赋值给next。当存到一定的值后，会扩展空间。

查询的时候将key进行计算得到（1-15），然后查询对应位置，一直去next，知道取到数据或结束。

4.1构造函数。

public HashMap() {
        //一个倍数 0.75f
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        //临界值 16*0.75=12，表示存了12个值以后要开辟新的空间
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        //初始空间16
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        //init里面没有内容。
        init();
}

4.2 put方法

public V put(K key, V value) {
        //如果key为空，单独做插入操作。
        if (key == null)
            //插入key为null的值，返回之前此处的值。
            return putForNullKey(value);
        //计算hash值，下面的两个方法
        int hash = hash(key.hashCode());
        //根据hash值获得在数组中的位置
        int i = indexFor(hash, table.length);
        //循环位置。直到为空位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果包含key值和hash值都相等。
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                //将原有的键值对的value值替换。
                V oldValue = e.value;
                e.value = value;
                //这是替换要执行的方法，现在内部还没有处理。
                e.recordAccess(this);
                //将就得value返回。
                return oldValue;
            }
        }
        //这里代表这个key值要新加入这个map。
        //修改次数
        modCount++;
        //加入
        addEntry(hash, key, value, i);
        return null;
}
//添加一个空的key。添加到数组的0位置。
private V putForNullKey(V value) {
        //判断对应位置时候为空，
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            //对应key值不为空
            if (e.key == null) {
                //更新数据。
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                //返回被替换掉的值。
                return oldValue;
            }
        }
        modCount++;
        //添加一个0位置的。
        addEntry(0, null, value, 0);
        return null;
}
//添加一个键值对，传入对应hash值和数组位置。
void addEntry(int hash, K key, V value, int bucketIndex) {
        //将这个位置的原有值取出来，
	Entry<K,V> e = table[bucketIndex];
        //新建一个，传入hash值，还有它的下一个键值对。所以同一个位置，后面插入的数据会查询快一点点。
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        //如果size大于临界值。
        if (size++ >= threshold)
            //将原来空间扩大为两倍
            resize(2 * table.length);
}
//开辟新空间
void resize(int newCapacity) {
        Entry[] oldTable = table;
        //旧数组的长度
        int oldCapacity = oldTable.length;
        //最大空间数。
        if (oldCapacity == MAXIMUM_CAPACITY) {
            //边界值为int的最大值。
            threshold = Integer.MAX_VALUE;
            //结束。
            return;
        }
        //新建一个数组,大小为传入的数字。
        Entry[] newTable = new Entry[newCapacity];
        //转移新数组
        transfer(newTable);
        //给table赋值。
        table = newTable;
        //边界值更新。
        threshold = (int)(newCapacity * loadFactor);
}
//将数据全部重新插入新数组，规则使用新得数组空间值计算。
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];
            //为空的键值对不用另外做处理
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    //根据hash值获取对应数组位置。
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
}

4.3 get方法

//获取key值对应信息。
public V get(Object key) {
        //key为null时候
        if (key == null)
            //直接从0号位置开始查。
            return getForNullKey();
        //计算key值对应hash。
        int hash = hash(key.hashCode());
        //使用indexFor计算出对应table的位置，然后开始遍历。直到找到或者结束。
        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值为null的value。
private V getForNullKey() {
        //先查找0号位，然后依次找next，直到找到key为null的值或键值对为空，返回。
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
}

4.4一些常用的方法

4.4.1 public boolean containsKey(Object key)

将key进行hash计算，然后找到键值对，然后返回结果

4.4.2 public boolean containsValue(Object value)

遍历数组，知道找到value。很费性能。

4.4.3  public void clear()

遍历数组，全部置为null。

4.4.4 public V remove(Object key)

找出对应key，去掉，更新关联值。

4.4.5 public Set<K> keySet()

将整个数组返回，这个Set是单独实现的一个类，里面重新实现了迭代器 ，size，包含，清除，将迭代的结果返回Map的key。其实就是返回了完整的Map内容。没有开辟任何多余空间，所以这个方法会很快。

4.4.6 public Collection<V> values()

这个和上面的一样，直接返回的是Map的整体数据，将Collection实现了迭代器 ，size，包含，清除，将迭代的结果返回Map的value。

 

5.使用的hash算法

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
        return h & (length-1);
}

计算都是通过hashCode来计算，所以存入HashMap的对象最好不要将hashCode写成一个值。hashCode各个类都有自己的生成方法，似乎Object默认的是内存位置，但是刚刚观察Integer和String都覆写了的。

int占32位，无符号左移20位，空位补0，无符号右移20位。算了，这个二进制运算符要系统的看，先这样把。

6.结束

看到这里都差不多了，主要是理解HashMap的结构和hash算法。

同时产生了两个疑问，先记下来。

疑问一：只实现抽象类AbstractMap不行么？为什么还要implements Map ，不重复吗？

疑问二：transient volatile 这样声明变量是为什么？