HashSet(底层)如何保证其唯一性

案例:

package set;

import java.util.HashSet;


public class HashSetDemo {
	public static void main(String[] args) {
		// 创建集合对象
		HashSet<String> hs = new HashSet<String>();

		// 创建并添加元素
		hs.add(\"hello\");
		hs.add(\"world\");
		hs.add(\"java\");
		hs.add(\"world\");

		// 遍历集合
		for (String s : hs) {
			System.out.println(s);
		}
	}
}

输出结果

hello
java
world

那么HashSet如何保证其元素唯一性?

源码

  HashSet的无参构造和add()方法的源码

//HashSet的无参构造可以看出实例化了一个HashMap
public HashSet() {
	map = new HashMap<E,Object>();
  }


//HashSet的add(E e)方法可以看出使用HashMap的put(...)方法
 public boolean add(E e) {
	return map.put(e, PRESENT)==null;
  }

由此可见其实HashSet的唯一性是靠HashMap来实现的

其实HashSet的底层数据结构和HashMap的底层数据结构一样都是哈希表

HashMap简单介绍

HashMap的底层结构是哈希表具体请参考(https://blog.csdn.net/P_Doraemon/article/details/80353579)

哈希表是有数组和单链表组成  

数组和单链表的元素都是一样的 -- Entry(key,value,hash,next)

HashSet的add()方法继续剖析

HashSet的add()方法是由HashMap的put方法实现
 public boolean add(E e) {
	return map.put(e, PRESENT)==null;
  }

//map.put(e, PRESENT)源码
 public V put(K key, V value) {
        //判断添加进HashSet的元素是否为null
        if (key == null)
            return putForNullKey(value);
        //跟据hash算法获取hash值(其实只要知道和对象的hashCode()方法相关)
        int hash = hash(key.hashCode());
        //获取哈希表中的数组的下标索引值(只要知道与hash值有关)
        int i = indexFor(hash, table.length);
        //遍历table[i]下的单链表的元素 -- Entry(只要知道与hash值有关)
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //比较新添加的元素与table[i]下的单链表的元素的hash值和(地址值或者内容值)
            //若值相同则表示元素重复  -- 只要知道不会将该元素添加到HashSet中
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //元素不相同则会将元素添加到HashSet中
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

在上面源码解释中可以看到判断元素是否重复与元素的hash值和(地址值或者内容值)有关

hash值由添加元素的hashCode()方法有关  内容值由添加元素的equals()方法有关 

步骤

步骤:
 		先看hashCode()值是否相同
 			相同:继续走equals()方法
 				返回true:说明元素重复,不添加
 				返回false:说明元素不重复,则添加到集合中去
 			不同:就直接把元素添加到集合中去
 		如果类没有重写这两个方法,默认使用Object()。一般来说不相同。因为之比较地址值
 		而String类重写了hashCode()和equals()方法，所以他就可以把相同的字符串去掉,之保留其中一个