欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

HashMap源码理解

程序员文章站 2022-04-30 15:16:00
...

看看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 这样声明变量是为什么？

 

相关标签： HashMap 源码 java Map

上一篇： 计算字符串相似度算法——Levenshtein

下一篇： 《4点起床-最养生和高效的时间管理》读书笔记

推荐阅读