1. 9IM首页
  2. 热点

HashSet和HashMap的区别

HashMap主要是用于存储非重复键值对,HashSet存储非重复的对象。虽然HashMap是继承于AbstractMap,实现了Map接口,HashSet继承于AbstractSet,实现了Set接口。但是由于它们都有去重的需求,所以HashSet主要实现都是基于HashMap的(如果需要复用一个类,我们可以使用继承模式,也可以使用组合模式。组合模式就是将一个类作为新类的组成部分,以此来达到复用的目的。)例如,在HashSet类中,有一个HashMap类型的成员变量map,这就是组合模式的应用。

    public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();//占位对象
    public HashSet() {
        map = new HashMap<>();
    }
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;//占位对象
    }
}

在HashSet的构造方法中,创建了一个HashMap,赋值给map属性,之后在添加元素时,就是将元素作为key添加到HashMap中,只不过value是一个占位对象PRESENT。除了 clone()writeObject()readObject()是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。那么HashMap又是如何实现key不重复的呢?

在调用HashMap的putVal方法添加新的键值对时,会进行如下操作:

1.根据key计算hash值。

2.根据hash值映射数组下标,然后获取数组下标的对应的元素。

3.数组下标存储的是一个链表,链表包含了哈希冲突的元素,会对链表进行遍历,判断hash1==hash2,除此以外,还必须要key1==key2,或者key1.equals(key2)。

因为两个不同的对象的hashCode可能相等,但是相同的对象的hashCode肯定相等,

==是判断两个变量或实例是不是指向同一个内存地址,如果是同一个内存地址,对象肯定相等。

int hash = hash(key);//根据key计算hash值
p = tab[i = (n - 1) & hash];//根据hash值映射数组下标,然后获取数组下标的对应的元素。
for (int binCount = 0; ; ++binCount) {//数组下标存储的是一个链表,链表包含了哈希冲突的元素,会对链表进行遍历,判断每个节点的hash值与插入元素的hash值是否相等,并且是存储key对象的地址相等,或者key相等。
if (e.hash == hash &&
	((k = e.key) == key || (key != null && key.equals(k))))
		break;
		p = e;
}

原创文章,作者:9IM,如若转载,请注明出处:https://www.9im.cn/671.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注