文章目录
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 < 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 < E , Object > ( ) ;
}
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) ;
}
public Iterator < E > iterator ( ) {
return map. keySet ( ) . iterator ( ) ;
}
public int size ( ) {
return map. size ( ) ;
}
public boolean isEmpty ( ) {
return map. isEmpty ( ) ;
}
public boolean contains ( Object o) {
return map. containsKey ( o) ;
}
public boolean add ( E e) {
return map. put ( e, PRESENT ) == null ;
}
public boolean remove ( Object o) {
return map. remove ( o) == PRESENT ;
}
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 ( ) {
}
public Person ( String name, int age) {
super ( ) ;
this . name = name;
this . age = age;
}
@Override
public int hashCode ( ) {
System . out. println ( "--------" ) ;
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 ( ) {
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() 比较的标准。