HashSet底层实现原理

短命女 2022-12-28 11:21 268阅读 0赞

HashSet 的内部采用了HashMap作为数据存储，HashSet其实就是在操作HashMap的key

1.  因为HashMap是无序的，因此HashSet也不能保证元素的顺序
2.  因为HashSet中没有对应同步的操作，因此是线程不安全的
3.  支持null元素(因为hashMap也支持null键和null值)

public class HashSet<E>   
     extends AbstractSet<E>   
     implements Set<E>, Cloneable, java.io.Serializable   
    {   
     // 使用 HashMap 的 key 保存 HashSet 中所有元素  
     private transient HashMap<E,Object> map;   
     // 定义一个虚拟的 Object 对象作为 HashMap 的 value   
     private static final Object PRESENT = new Object();   
     …   
     // 构造方法，初始化 HashSet，底层会初始化一个 HashMap   
     public HashSet()   
     {   
         map = new HashMap<E,Object>();   
     }   
     // 以指定的 initialCapacity、loadFactor 创建 HashSet   
     // 其实就是以相应的参数创建 HashMap   
     public HashSet(int initialCapacity, float loadFactor)   
     {   
         map = new HashMap<E,Object>(initialCapacity, loadFactor);   
     }   
     public HashSet(int initialCapacity)   
     {   
         map = new HashMap<E,Object>(initialCapacity);   
     }   
     HashSet(int initialCapacity, float loadFactor, boolean dummy)   
     {   
         map = new LinkedHashMap<E,Object>(initialCapacity   
             , loadFactor);   
     }   
     // 调用 map 的 keySet 来返回所有的 key   
     public Iterator<E> iterator()   
     {   
         return map.keySet().iterator();   
     }   
     // 调用 HashMap 的 size() 方法返回 Entry 的数量，就得到该 Set 里元素的个数  
     public int size()   
     {   
         return map.size();   
     }   
     // 调用 HashMap 的 isEmpty() 判断该 HashSet 是否为空，  
     // 当 HashMap 为空时，对应的 HashSet 也为空  
     public boolean isEmpty()   
     {   
         return map.isEmpty();   
     }   
     // 调用 HashMap 的 containsKey 判断是否包含指定 key   
     //HashSet 的所有元素就是通过 HashMap 的 key 来保存的  
     public boolean contains(Object o)   
     {   
         return map.containsKey(o);   
     }   
     // 将指定元素放入 HashSet 中，也就是将该元素作为 key 放入 HashMap   
     public boolean add(E e)   
     {   
         return map.put(e, PRESENT) == null;   
     }   
     // 调用 HashMap 的 remove 方法删除指定 Entry，也就删除了 HashSet 中对应的元素  
     public boolean remove(Object o)   
     {   
         return map.remove(o)==PRESENT;   
     }   
     // 调用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素  
     public void clear()   
     {   
         map.clear();   
     }   
     …   
    }

>  
> 
> ## HashSet中没有重复元素，允许有一个为null ##
> 
> HashSet底层使用了哈希表来支持的，特点：存储快  
> 往Haset添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值 ，然后通过元素 的哈希值经过移位等运算，就可以算出该元素在哈希表中 的存储位置。  
> 1.如果算出的元素存储的位置目前没有任何元素存储，那么该元素可以直接存储在该位置上  
> 2. 如果算出的元素的存储位置目前已经存在有其他的元素了，那么还会调用该元素的equals方法  
> 与该位置的元素再比较一次，如果equals方法返回的是true，那么该位置上的元素视为重复元  
> 素，不允许添加，如果返回的是false，则允许添加

class Person {
    	String name;
    	int age;
    	private void Peron() {
    		// TODO Auto-generated method stub
    
    	}
    
    	public Person(String name, int age) {
    		super();
    		this.name = name;
    		this.age = age;
    	}
    
    	@Override
    	public int hashCode() {
    		System.out.println("--------");
    		// TODO Auto-generated method stub
    		return this.age;
    	}
    
    	@Override
    	public boolean equals(Object obj) {
    		System.out.println("---****----");
    		Person p = (Person)obj;
    		return this.age == p.age;
    	}
    
    	@Override
    	public String toString() {
    		// TODO Auto-generated method stub
    		return "{姓名："+name+"年龄："+age+"}";
    	}
    }
    public class Demo2 {
    	public static void main(String[] args) {
    		HashSet set = new HashSet();
    		set.add(new Person("yy",18));
    		set.add(new Person("xx",19));
    		set.add(new Person("zz",20));
    		set.add(new Person("jj",25));
    		System.out.println("添加元素成功了嗎？"+set.add(new Person("zhangsan",18)));
    		System.out.println("集合的元素："+set);
    	}
    }

## HashSet实现原理进行一个总结： ##

（1）基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

（2）当我们试图把某个类的对象当成 HashMap的 key，或试图将这个类的对象放入 HashSet 中保存时，重写该类的equals(Object obj)方法和 hashCode() 方法很重要，而且这两个方法的返回值必须保持一致：当该类的两个的 hashCode() 返回值相同时，它们通过 equals() 方法比较也应该返回 true。通常来说，所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。

（3）HashSet的其他操作都是基于HashMap的。

[HashSet底层实现原理][HashSet]

[Java面试题之HashSet 的实现原理？][Java_HashSet]

[HashSet]: https://blog.csdn.net/weixin_42549988/article/details/89577891?utm_source=app
[Java_HashSet]: https://blog.csdn.net/qq_41026809/article/details/90449073?utm_source=app