文章目录
10.HashSet底层实现原理10.1HashSet特点10.2HashSet源码10.3 add流程10.4总结
10.HashSet底层实现原理
10.1HashSet特点
存储对象:HashSet 存储对象采用哈希表的方式,它不允许重复元素,即集合中不会包含相同的元素。当向 HashSet 中添加元素时,会根据元素的 hashCode() 方法和 equals() 方法来判断元素是否重复。底层数据结构:HashSet 的底层数据结构是基于 HashMap 实现的,实际上 HashSet 的元素就是作为 HashMap 的 key 存储的。null 值问题:HashSet 允许存储一个 null 元素。线程安全问题:不安全
10.2HashSet源码
public class HashSet
// 使用 HashMap 的 key 保存 HashSet 中所有元素
private transient HashMap
// 定义一个虚拟的 Object 对象作为 HashMap 的 value
private static final Object PRESENT = new Object();
…
// 构造方法,初始化 HashSet,底层会初始化一个 HashMap
public HashSet(){
map = new HashMap
}
// 以指定的 initialCapacity、loadFactor 创建 HashSet
// 其实就是以相应的参数创建 HashMap
public HashSet(int initialCapacity, float loadFactor){
map = new HashMap
}
public HashSet(int initialCapacity){
map = new HashMap
}
HashSet(int initialCapacity, float loadFactor, boolean dummy){
map = new LinkedHashMap
, loadFactor);
}
// 调用 map 的 keySet 来返回所有的 key
public 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();
}
…
}
10.3 add流程
HashSet底层使用了哈希表来支持的,特点:存储快;往Haset添加元素的时候,HashSet会先调用元素的hashCode方法得到元素的哈希值 ,然后通过元素的哈希值经过移位等运算,就可以算出该元素在哈希表中的存储位置。
如果算出的元素存储的位置目前没有任何元素存储,那么该元素可以直接存储在该位置上;如果算出的元素的存储位置目前已经存在有其他的元素了,那么还会调用该元素的equals方法; 与该位置的元素再比较一次,如果equals方法返回的是true,那么该位置上的元素视为重复元 素,不允许添加,如果返回的是false,则允许添加 例子:该对象的 age 字段与之前已经添加的一个 age 字段为 18 的对象相同,且哈希码也相同,所以 HashSet 认为它们是同一个对象,因此不会将其添加到集合中,返回的结果是 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);
}
}
10.4总结
存储对象:HashSet 存储对象采用哈希表的方式,它不允许重复元素,即集合中不会包含相同的元素。当向 HashSet 中添加元素时,会根据元素的 hashCode() 方法和 equals() 方法来判断元素是否重复。底层数据结构:HashSet 的底层数据结构是基于 HashMap 实现的,实际上 HashSet 的元素就是作为 HashMap 的 key 存储的。null 值问题:HashSet 允许存储一个 null 元素。线程安全问题:不安全当我们试图把某个类的对象当成 HashMap的 key,或试图将这个类的对象放入 HashSet 中保存时,重写该类的equals(Object obj)方法和 hashCode() 方法很重要,而且这两个方法的返回值必须保持一致:当该类的两个的 hashCode() 返回值相同时,它们通过 equals() 方法比较也应该返回 true。通常来说,所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。
精彩文章
发表评论