84669 person learning
152542 person learning
20005 person learning
5487 person learning
7821 person learning
359900 person learning
3350 person learning
180660 person learning
48569 person learning
18603 person learning
40936 person learning
1549 person learning
1183 person learning
32909 person learning
List可以包括ArrayList和LinkedList
在增、删、查的速度上明显Set快
不知道HashSet的遍历是怎么实现的?
顺便问一句,Java里HashSet是怎么解决冲突的元素的?即被hash到同一个格子里的元素。还是说默认不会hash到同一个值,就不解决了?
认证0级讲师
java是开源的,可以直接看源码。
而且对于一个java程序员来说,JDK里面的集合框架是必看的。
--------- 答案被忽略了,因此新增点儿内容(2014年11月6日) ---------------
HashSet 源码:
HashSet
public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable
HashSet 内部使用了 HashMap:
HashMap
private transient HashMap map;
如果使用一个已经有的集合来初始化 HashSet:
/** * Constructs a new set containing the elements in the specified * collection. The HashMap is created with default load factor * (0.75) and an initial capacity sufficient to contain the elements in * the specified collection. * * @param c the collection whose elements are to be placed into this set * @throws NullPointerException if the specified collection is null */ public HashSet(Collection extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); }
默认的加载因子为 0.75。这个数值已常量 DEFAULT_LOAD_FACTOR 的方式定义在 HashMap 中。
DEFAULT_LOAD_FACTOR
现在重点来了,添加元素:
我使用的是最新的1.8版本,代码相对于1.6版都重写了,又得重新看一遍了
/** * 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[] tab; Node 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 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)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 无疑是速度快不少。(至此回答了问题1,为什么 Set 比 List 快?)
Set
List
由于 gist 被墙了,于是贴到了 chopapp:注释版HashMap
java是开源的,可以直接看源码。
而且对于一个java程序员来说,JDK里面的集合框架是必看的。
--------- 答案被忽略了,因此新增点儿内容(2014年11月6日) ---------------
HashSet
源码:定义
HashSet
内部使用了HashMap
:如果使用一个已经有的集合来初始化
HashSet
:默认的加载因子为 0.75。这个数值已常量
DEFAULT_LOAD_FACTOR
的方式定义在HashMap
中。现在重点来了,添加元素:
我使用的是最新的1.8版本,代码相对于1.6版都重写了,又得重新看一遍了
看中间部分代码。如果key相同,则新value替换旧的。否则继续找next。如果hash不同,则肯定不同;如果hash相同,则不一定相同。相对于直接比较 key 的容器,
HashMap
无疑是速度快不少。(至此回答了问题1,为什么Set
比List
快?)由于 gist 被墙了,于是贴到了 chopapp:注释版HashMap