数据结构 - Java中List和HashSet的遍历速度有差别吗？

Question

List可以包括ArrayList和LinkedList

在增、删、查的速度上明显Set快

不知道HashSet的遍历是怎么实现的？

顺便问一句，Java里HashSet是怎么解决冲突的元素的？即被hash到同一个格子里的元素。还是说默认不会hash到同一个值，就不解决了？

Answer 1

Java is open source, you can view the source code directly.

And for a Java programmer, the collection framework in the JDK is a must-see.

--------- The answer was ignored, so I added some content (November 6, 2014) ---------------

HashSet Source code:

Definition

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

HashSet internally uses HashMap:

private transient HashMap<E,Object> map;

If you use an existing collection to initialize HashSet:

/**
 * Constructs a new set containing the elements in the specified
 * collection.  The <tt>HashMap</tt> 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);
}

The default load factor is 0.75. This value is defined in DEFAULT_LOAD_FACTOR as a constant HashMap.

Now comes the point, add elements:

I am using the latest version 1.8. The code has been rewritten compared to version 1.6. I have to read it again

/**
 * 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;
}

Look at the middle part of the code. If the keys are the same, the new value replaces the old one. Otherwise, continue to find next. If the hashes are different, they must be different; if the hashes are the same, they are not necessarily the same. Compared with directly comparing key containers, HashMap is undoubtedly much faster. (Question 1 has been answered so far. Why is Set faster than List?)

Since the gist was blocked, I posted it to chopapp: Annotated HashMap