HashSet是Set接口的一个具体实现类之一,它内部采用哈希算法,专门为快速查找而设计,它不允许插入重复的值,需要注意的问题是,存入HashSet的对象必须定义hashCode和equals方法。
下面我们来谈谈HashSet如何判定两个对象是否重复。
HashSet内部使用HashMap来保存对象,将需要存入的对象比如T a,以key的形式存入HashMap中,这可以从代码中看到:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
首先,说下HashMap内部是使用数组进行存储的,数组里存放的是HashMap的内部类Entry,它是一个自引用的类,支持链表结构,用于对哈希冲突的情况下保存多个对象。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
.........//略去大段代码
}
然后我们在HashMap的put方法中可以看到它是如何进行重复性判断的:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
首先,可以通过key的hashCode,经过hash()函数的处理,得出一个i,这是这个对象应该存放的位置,然后去数组中查找第一个Entry,如何Entry不存在,直接进行添加操作;如果发现存在Entry,便对其进行遍历,使用条件(k = e.key) == key || key.equals(k)进行判断,如果为true,说明已经存在,便对其进行重新设置,但是因为hashSet使用的其实是key,value对其是没任何用处的。所以相当于没有任何改变。
这也就是我们为什么在使用HashSet存储自定义类时,需要重写hashCode()和equals()方法的原因,否则使用Object对象默认的hashCode()和equals方法,Object的hashCode()使用对象的地址计算散列码,使用内存地址进行equals()判定。这可能会出现你不想看到的结果。
分享到:
相关推荐
hash类存储结构(HashSet、HashMap等等)添加元素会有重复性校验,校验的方式就是先取hashCode判断是否相等(找到对应的位置,该位置可能存在多个元素),然后再取equals方法比较(极大缩小比较范围,高效判断),...
* 项目的难点:数据的测试、业务逻辑层的判定、用户界面的设计 总结 * Java 是一个非常重要的编程语言,需要掌握 Java 基础内容、Java 网络编程、JDBC 等知识点 * 项目经验是非常宝贵的,需要总结和反思项目经验,...
- Set(集合):元素无序、不可重复,主要实现类有 HashSet 和 TreeSet。 - Map(映射):存储键值对,元素成对出现,主要实现类有 HashMap 和 TreeMap。 14. **循环语句**:for 语句和 while 语句是循环控制结构...
HashMap允许null键但不允许null值(C错误),HashSet集合中的元素无序且不可重复(D错误)。 20. **C程序执行**:C语言可执行程序的开始执行点是main()函数(C)。 21. **字符数组初始化**:不正确的字符数组初始...
// 使用 HashSet 存储顶点,重复出现的顶点会被移除 if (!set.add(point1)) { set.remove(point1); } if (!set.add(point2)) { set.remove(point2); } if (!set.add(point3)) { set.remove(point3); } if...
### 全国信息学奥林匹克竞赛NOIP试题解析 #### 题一:级数求和(存盘名:NOIPC1) **知识点:** ...这些题目不仅考察了基本的数据结构与算法知识,还要求参赛者具备一定的逻辑思维能力和编程技巧。
5. **Set Data Structures**(集合):Java中的集合接口如`Set`,不包含重复元素,实现了如`HashSet`和`TreeSet`等不同的实现方式。 6. **Kd-Trees**(线段树):Kd树是一种在高维空间中存储点的平衡二叉树,适用于...