List可以包括ArrayList和LinkedList在增、删、查的速度上明显Set快不知道HashSet的遍历是怎么实现的?顺便问一句,Java里HashSet是怎么解决冲突的元素的?即被hash到同一个格子里的元素。还是说默认不会hash到同一个值,就不解决了?
java是开源的,可以直接看源码。而且对于一个java程序员来说,JDK里面的集合框架是必看的。
HashSet 源码:
定义
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
HashSet 内部使用了 HashMap:private transient HashMap<E,Object> map;
如果使用一个已经有的集合来初始化 HashSet:
默认的加载因子为 0.75。这个数值已常量 DEFAULT_LOAD_FACTOR 的方式定义在 HashMap 中。
现在重点来了,添加元素:
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
看中间部分代码。如果key相同,则新value替换旧的。否则继续找next。如果hash不同,则肯定不同;如果hash相同,则不一定相同。相对于直接比较 key 的容器,HashMap 无疑是速度快不少。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。