类介绍

类定位

本类对List中的方法做了基本实现，注意：实现此接口的是随机访问类数组，不是顺序访问类的数组

注：

• 顺序访问类数组是指a[0]和a[100]访问需要的时间是不同的，一般访问的时间会随着数组下标递增。
• 随机访问类数组是指a[0]和a[100]访问用时相同

类继承关系分析

还是上idea的截图：

1.png

它是继承自AbstractCollection的，并实现了接口List，如果继承AbstractList就等于是实现了List接口。此类对List中相对于Collection独有的方法进行了实现。

类使用场景

• 要实现List
• 希望少耗时
• 没有必须继承的父类
• 要实现的是随机访问类数组
• 不支持多线程

类注意事项

需要你自己实现的方法和场景的匹配如下表所示：

源码介绍

此类的实现内容有点多，我们先从数据结构讲起，也就是内部类。然后介绍它实现的默认方法，也就是内部类的使用。

内部类介绍

Itr

源码

  private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.remove(lastRet);
                if (lastRet < cursor)
                    cursor--;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException e) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

类定位

此类对Iterator中的方法进行了实现，最重要的是进行了fail-fast机制的异常抛出：因为这里定义了expectedModCount，这里先留着，在问题思考中，我们会详细介绍此类是如何判断多个线程在同时操纵此类。

类继承关系分析

直接实现了Iterator。

重点方法

next()

注意此方法进行了数组是否发生变化的检查。

remove()

1. 次数组也在进行数组是否发生变化的检查
2. 在修改完数组后有一行expectedModCount = modCount;，即我修改完成了，修改一下变量：
   1. 在我修改时访问数组的线程一定会有expectedModCount == modCount为false，因为我调用的AbstractList的remove()中对modCount进行了+1操作，此时进行数组访问的线程会抛出ConcurrentModificationException
   2. 在我修改结束后访问的线程由于我进行了``expectedModCount = modCount`操作，它检查的结果是访问期间没有改变，可以正常访问。

checkForComodification()

判断的思路很简单，就是modCount == expectedModCount,在问题思考中我们会进行详细介绍。

使用场景

此实现类用来为AbstractList的iterator()方法提供返回的对象类型，此类依赖AbstractList的size(),remove(),get()三个方法。

ListIterator

源码

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public E previous() {
            checkForComodification();
            try {
                int i = cursor - 1;
                E previous = get(i);
                lastRet = cursor = i;
                return previous;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor-1;
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                AbstractList.this.set(lastRet, e);
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                AbstractList.this.add(i, e);
                lastRet = -1;
                cursor = i + 1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

类定位

我们知道ListIterator是Iterator接口的子类，这个类在Iterator的基础上增加了向前遍历、增加、修改三个功能。

类继承关系分析

2.png

没啥可说的。

重点方法

没啥新鲜的东西，注意原则有两个：

1. 所有的操作前都要检查数组是否有改动
2. 如果对数组做了修改，在调用AbstractList的修改之后记得使用expectedModCount = modCount将修改次数进行同步，使后面访问数组的操作能正常进行

使用场景

此类是为AbstractList的listIterator()的返回结果定义的数据结构，依赖AbstractList中的set(),get(),remove(),size()方法

SubList

源码

class SubList<E> extends AbstractList<E> {
    private final AbstractList<E> l;
    private final int offset;
    private int size;

    SubList(AbstractList<E> list, int fromIndex, int toIndex) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > list.size())
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
        l = list;
        offset = fromIndex;
        size = toIndex - fromIndex;
        this.modCount = l.modCount;
    }

    public E set(int index, E element) {
        rangeCheck(index);
        checkForComodification();
        return l.set(index+offset, element);
    }

    public E get(int index) {
        rangeCheck(index);
        checkForComodification();
        return l.get(index+offset);
    }

    public int size() {
        checkForComodification();
        return size;
    }

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        checkForComodification();
        l.add(index+offset, element);
        this.modCount = l.modCount;
        size++;
    }

    public E remove(int index) {
        rangeCheck(index);
        checkForComodification();
        E result = l.remove(index+offset);
        this.modCount = l.modCount;
        size--;
        return result;
    }

    protected void removeRange(int fromIndex, int toIndex) {
        checkForComodification();
        l.removeRange(fromIndex+offset, toIndex+offset);
        this.modCount = l.modCount;
        size -= (toIndex-fromIndex);
    }

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        int cSize = c.size();
        if (cSize==0)
            return false;

        checkForComodification();
        l.addAll(offset+index, c);
        this.modCount = l.modCount;
        size += cSize;
        return true;
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(final int index) {
        checkForComodification();
        rangeCheckForAdd(index);

        return new ListIterator<E>() {
            private final ListIterator<E> i = l.listIterator(index+offset);

            public boolean hasNext() {
                return nextIndex() < size;
            }

            public E next() {
                if (hasNext())
                    return i.next();
                else
                    throw new NoSuchElementException();
            }

            public boolean hasPrevious() {
                return previousIndex() >= 0;
            }

            public E previous() {
                if (hasPrevious())
                    return i.previous();
                else
                    throw new NoSuchElementException();
            }

            public int nextIndex() {
                return i.nextIndex() - offset;
            }

            public int previousIndex() {
                return i.previousIndex() - offset;
            }

            public void remove() {
                i.remove();
                SubList.this.modCount = l.modCount;
                size--;
            }

            public void set(E e) {
                i.set(e);
            }

            public void add(E e) {
                i.add(e);
                SubList.this.modCount = l.modCount;
                size++;
            }
        };
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new SubList<>(this, fromIndex, toIndex);
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkForComodification() {
        if (this.modCount != l.modCount)
            throw new ConcurrentModificationException();
    }
}

类定位

一个AbstractList的子类，是为了subList()返回的结果而定义的数据结构。

类继承关系分析

3.png

重点方法

没啥，可以把他当作AbstractList的一个标准实现规范。唯一难以理解的有两点：

1. SubList是为AbstractList的subList()方法定义的，因为必须是List的实现类，所以它很干脆的直接继承了AbstractList，他没有重写AbstractList的subList()方法，所以被返回的SubList如果调用subList()还是调用的父类的生成它的subList()方法
2. SubList中为了检测数组是否被其他线程修改使用的方法是：
   1. 自己的父类AbstractList有一个modCount
   2. 将生成自己的AbstractList存在自己的l属性中
   3. 自己的set(),remove()操作都依赖自己l中存储的AbstractList的方法，通过判断super.modCount和l.modCount是否相等可以判断是否在自己访问的过程中被修改过

问题：这里l的类型是AbstractList真的能表示所有情况吗？是不是用List更好些？

答案见问题思考

使用场景

它只有SubList(AbstractList<E> list, int fromIndex, int toIndex)一个构造方法，所以只能在求子类的方法中做返回的数据类型

RandomAccessSubList

源码

class RandomAccessSubList<E> extends SubList<E> implements RandomAccess {
    RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) {
        super(list, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

类定位

如果是普通的List则返回SubList，也就是一个普通的AbstructList的实现类；如果调用subList的List实现了RandomAccess（也就是说可以用for(int i=0;i<a.length;i++)的List），那么返回的是RandomAccessSubList。

类继承关系分析

4.png

总体来说，就是同时实现了RandomAccess和List接口。

重点方法

无

使用场景

类定位中说了

方法、变量介绍

add()系列方法

方法列表：

• public boolean add(E e)
• public void add(int index, E element)
• public boolean addAll(int index, Collection<? extends E> c)
• public boolean addAll(Collection<? extends E> c)

其中最根本的实现方法在public void add(int index, E element)中，等待程序员去实现。

remove()系列方法

方法列表：

• E remove(int index);
• boolean remove(Object o);
• boolean removeAll(Collection<?> c);
• protected void removeRange(int fromIndex, int toIndex)
• public void clear()

其中removeAll()等批量操作依赖removeRange()，最后又依赖remove(int)，等待程序员实现。

注意：AbstractList中没有对remove(Object)进行实现，这个接口在AbstractCollection()中进行了实现，它依赖itreator()返回的结果的remove()方法，而这个方法又依赖AbstractList的remove(int)方法。综上，remove()相关的方法只需要实现remove(int)方法即可。

轮询相关方法

没得说，都是依赖listIterator()的方法。轮询呗。

public int indexOf(Object o)

public int lastIndexOf(Object o)

abstract public E get(int index);

和内部类相关的方法

public Iterator<E> iterator()

依赖Itr

public ListIterator<E> listIterator()

依赖ListIterator

public ListIterator<E> listIterator(final int index)

依赖ListIterator

public List<E> subList(int fromIndex, int toIndex)

依赖SubList/RandomAccessSubList

Object相关方法

public int hashCode()

注意，hashCode是用来表征对象特征的一个特征码，它不用于equals的判断。hashCode相同不一定代表对象相同，因为即使两个对象没什么关系，也可能计算出来的hashCode一样，当然如何避免这种情况发生，java还是采用了很多方法的,上源码：

    public int hashCode() {
        int hashCode = 1;
        for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        return hashCode;
    }

至于为什么这么计算，参见问题思考。

public boolean equals(Object o)

先上源码：

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }

判断思路：

1. 先看this指针指的和o指的是不是一块地方，如果是那就是了
2. 判断传入的对象是不是List的实现类，List只能和List相等，其他的不要想了
3. 如果都是List判断里面的元素是不是一一相等，注意啦：要元素和顺序同时相等

问题思考

modCount工作原理

源码解释

    /**
     * The number of times this list has been <i>structurally modified</i>.
     * Structural modifications are those that change the size of the
     * list, or otherwise perturb it in such a fashion that iterations in
     * progress may yield incorrect results.
     *
     * <p>This field is used by the iterator and list iterator implementation
     * returned by the {@code iterator} and {@code listIterator} methods.
     * If the value of this field changes unexpectedly, the iterator (or list
     * iterator) will throw a {@code ConcurrentModificationException} in
     * response to the {@code next}, {@code remove}, {@code previous},
     * {@code set} or {@code add} operations.  This provides
     * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
     * the face of concurrent modification during iteration.
     *
     * <p><b>Use of this field by subclasses is optional.</b> If a subclass
     * wishes to provide fail-fast iterators (and list iterators), then it
     * merely has to increment this field in its {@code add(int, E)} and
     * {@code remove(int)} methods (and any other methods that it overrides
     * that result in structural modifications to the list).  A single call to
     * {@code add(int, E)} or {@code remove(int)} must add no more than
     * one to this field, or the iterators (and list iterators) will throw
     * bogus {@code ConcurrentModificationExceptions}.  If an implementation
     * does not wish to provide fail-fast iterators, this field may be
     * ignored.
     */
    protected transient int modCount = 0;

个人理解

首先，大概总结一下jdk源码中的注释：

1. modCount指的是List中的数据修改的次数。
2. 这个变量在iterator(),listIterator()返回的对象中使用。
3. 此变量帮助提供了一种fail-fast的机制。
4. 这个变量的使用是可以选择的，如果你不希望提供fail-fast，可以不用它。

我们从一个场景中理解一下：

我有一个AbstractList的子类TestShowList，它只是对最基本的增删改操作做了支持。

我要对这个TestShowList进行遍历，我用for-each进行遍历，最底层的实现肯定是调用了iterator()获得一个Iterator然后进行遍历。在我们获得Iterator时会有int expectedModCount = modCount;的同步操作。加入我们在遍历时进行了修改，会有以下几种情况：

1. 如果是直接调用的TestShowList的增删改进行的修改，由于Iterator和TestShowList是在同一个地方存储的数据，所以会受到影响：表现为TestShowList的modCount++，在遍历时expectedModCount == modCount不再成立。
2. 如果是调用Iterator的操作进行的：
   • 单线程：
     • 如果是调用本实例的remove()方法，它会自己同步expectedModCount = modCount，不会报错
     • 如果在一个线程中通过iterator()获得了多个Iterator实例，用其他的实例对集合修改，modCount修改后不会同步到本实例，会报错
   • 多线程：
     • 当然，如果用其他Iterator实例的remove()会报错
     • 如果用同一Iterator实例的remove()进行修改。对modCount == expectedModCount的检测可能在modCount修改和expectedModCount的同步之间，会报错。

以上是我从注释加源码一起分析出来的。对各种情况都做了介绍，当然，网上还有比较笼统的说法：单线程不报错，多线程报错。这种说法指的应该是默认采用同一Iterator实例的remove()进行的操作。

注意：报错是出现问题，但是出问题不一定能抛出错误，你不能把所有的希望都寄托于抛异常报错，这个是不可靠的。

fail-fast机制

fail-fast是java集合类中提供的一种异常抛出机制，即：在遍历集合的过程中发现集合被改变了，就抛出ConcurrentModificationException。

fail-fast检测的方法在上一节我们详细介绍过了。fail-fast中对集合元素的遍历、修改是在同一个副本上的。所以才会有遍历时被修改的情况。

还有一种fail-safe机制，即修改元素是在新的副本上进行的，它不会抛出ConcurrentModificationException，但是这种机制有两个问题：

1. 需要复制集合，产生大量的无效对象，开销大
2. 无法保证读取的数据是目前原始数据结构中的数据。

两种机制对比如下：

SubList中存储数组的是AbstractList，万一是直接实现List的类生成的它会怎么样

。。。脑子不好使了吧，如果没有继承AbstractList，又怎么会访问到他的内部类。。。。。。

jdk底层的这些代码写的挺严谨的，限制的恰到好处。

计算hashCode为什么采用31作为算子？

本文从SF中的文章找到了答案，作者写的很棒，为了查看方便就粘贴过来了，文章地址见附录。

算法介绍

hashCode的源码在上文中有介绍，计算的过程如下：

假设 n=3
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
       h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
       h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]

选择31的理由

第一，31是一个不大不小的质数，是作为 hashCode 乘子的优选质数之一。另外一些相近的质数，比如37、41、43等等，也都是不错的选择。那么为啥偏偏选中了31呢？请看第二个原因。

第二、31可以被 JVM 优化，31 * i = (i << 5) - i。

上面两个原因中，第一个需要解释一下，第二个比较简单，就不说了。下面我来解释第一个理由。一般在设计哈希算法时，会选择一个特殊的质数。至于为啥选择质数，我想应该是可以降低哈希算法的冲突率。至于原因，这个就要问数学家了，我几乎可以忽略的数学水平解释不了这个原因。上面说到，31是一个不大不小的质数，是优选乘子。那为啥同是质数的2和101（或者更大的质数）就不是优选乘子呢，分析如下。

这里先分析质数2。首先，假设 n = 6，然后把质数2和 n 带入上面的计算公式。并仅计算公式中次数最高的那一项，结果是2^5 = 32，是不是很小。所以这里可以断定，当字符串长度不是很长时，用质数2做为乘子算出的哈希值，数值不会很大。也就是说，哈希值会分布在一个较小的数值区间内，分布性不佳，最终可能会导致冲突率上升。

上面说了，质数2做为乘子会导致哈希值分布在一个较小区间内，那么如果用一个较大的大质数101会产生什么样的结果呢？根据上面的分析，我想大家应该可以猜出结果了。就是不用再担心哈希值会分布在一个小的区间内了，因为101^5 = 10,510,100,501。但是要注意的是，这个计算结果太大了。如果用 int 类型表示哈希值，结果会溢出，最终导致数值信息丢失。尽管数值信息丢失并不一定会导致冲突率上升，但是我们暂且先认为质数101（或者更大的质数）也不是很好的选择。最后，我们再来看看质数31的计算结果：31^5 = 28629151，结果值相对于32和10,510,100,501来说。是不是很nice，不大不小。

《Effective Java》中有一段话进行了介绍：

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: `31 * i == (i << 5) - i``. Modern VMs do this sort of optimization automatically.

选择数字31是因为它是一个奇质数，如果选择一个偶数会在乘法运算中产生溢出，导致数值信息丢失，因为乘二相当于移位运算。选择质数的优势并不是特别的明显，但这是一个传统。同时，数字31有一个很好的特性，即乘法运算可以被移位和减法运算取代，来获取更好的性能：31 * i == (i << 5) - i，现代的 Java 虚拟机可以自动的完成这个优化。

实验验证

实验方法

哈希冲突率计算

计算哈希算法冲突率并不难，比如可以一次性将所有单词的 hash code 算出，并放入 Set 中去除重复值。之后拿单词数减去 set.size() 即可得出冲突数，有了冲突数，冲突率就可以算出来了。当然，如果使用 JDK8 提供的流式计算 API，则可更方便算出，代码片段如下：

public static Integer hashCode(String str, Integer multiplier) {
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = multiplier * hash + str.charAt(i);
    }

    return hash;
}
    
/**
 * 计算 hash code 冲突率，顺便分析一下 hash code 最大值和最小值，并输出
 * @param multiplier
 * @param hashs
 */
public static void calculateConflictRate(Integer multiplier, List<Integer> hashs) {
    Comparator<Integer> cp = (x, y) -> x > y ? 1 : (x < y ? -1 : 0);
    int maxHash = hashs.stream().max(cp).get();
    int minHash = hashs.stream().min(cp).get();

    // 计算冲突数及冲突率
    int uniqueHashNum = (int) hashs.stream().distinct().count();
    int conflictNum = hashs.size() - uniqueHashNum;
    double conflictRate = (conflictNum * 1.0) / hashs.size();

    System.out.println(String.format("multiplier=%4d, minHash=%11d, maxHash=%10d, conflictNum=%6d, conflictRate=%.4f%%",
                multiplier, minHash, maxHash, conflictNum, conflictRate * 100));
}

作者的实验结果：

5.png

哈希值分布可视化

上一节分析了不同数字作为乘子时的冲突率情况，这一节来分析一下不同数字作为乘子时，哈希值的分布情况。在详细分析之前，我先说说哈希值可视化的过程。我原本是打算将所有的哈希值用一维散点图进行可视化，但是后来找了一圈，也没找到合适的画图工具。加之后来想了想，一维散点图可能不合适做哈希值可视化，因为这里有超过23万个哈希值。也就意味着会在图上显示超过23万个散点，如果不出意外的话，这23万个散点会聚集的很密，有可能会变成一个大黑块，就失去了可视化的意义了。所以这里选择了另一种可视化效果更好的图表，也就是 excel 中的平滑曲线的二维散点图（下面简称散点曲线图）。当然这里同样没有把23万散点都显示在图表上，太多了。所以在实际绘图过程中，我将哈希空间等分成了64个子区间，并统计每个区间内的哈希值数量。最后将分区编号做为X轴，哈希值数量为Y轴，就绘制出了我想要的二维散点曲线图了。这里举个例子说明一下吧，以第0分区为例。第0分区数值区间是[-2147483648, -2080374784)，我们统计落在该数值区间内哈希值的数量，得到 <分区编号, 哈希值数量> 数值对，这样就可以绘图了。分区代码如下：

 /**
 * 将整个哈希空间等分成64份，统计每个空间内的哈希值数量
 * @param hashs
 */
public static Map<Integer, Integer> partition(List<Integer> hashs) {
    // step = 2^32 / 64 = 2^26
    final int step = 67108864;
    List<Integer> nums = new ArrayList<>();
    Map<Integer, Integer> statistics = new LinkedHashMap<>();
    int start = 0;
    for (long i = Integer.MIN_VALUE; i <= Integer.MAX_VALUE; i += step) {
        final long min = i;
        final long max = min + step;
        int num = (int) hashs.parallelStream()
                .filter(x -> x >= min && x < max).count();

        statistics.put(start++, num);
        nums.add(num);
    }

    // 为了防止计算出错，这里验证一下
    int hashNum = nums.stream().reduce((x, y) -> x + y).get();
    assert hashNum == hashs.size();

    return statistics;
}

本文中的哈希值是用整形表示的，整形的数值区间是 [-2147483648, 2147483647]，区间大小为 2^32。所以这里可以将区间等分成64个子区间，每个自子区间大小为 2^26。详细的分区对照表如下：

接下来，让我们对照上面的分区表，对数字2、3、17、31、101的散点曲线图进行简单的分析。先从数字2开始，数字2对于的散点曲线图如下：

6.png

上面的图还是很一幕了然的，乘子2算出的哈希值几乎全部落在第32分区，也就是 [0, 67108864)数值区间内，落在其他区间内的哈希值数量几乎可以忽略不计。这也就不难解释为什么数字2作为乘子时，算出哈希值的冲突率如此之高的原因了。所以这样的哈希算法要它有何用啊，拖出去斩了吧。接下来看看数字3作为乘子时的表现：

7.png

3作为乘子时，算出的哈希值分布情况和2很像，只不过稍微好了那么一点点。从图中可以看出绝大部分的哈希值最终都落在了第32分区里，哈希值的分布性很差。这个也没啥用，拖出去枪毙5分钟吧。在看看数字17的情况怎么样：

8.png

数字17作为乘子时的表现，明显比上面两个数字好点了。虽然哈希值在第32分区和第34分区有一定的聚集，但是相比较上面2和3，情况明显好好了很多。除此之外，17作为乘子算出的哈希值在其他区也均有分布，且较为均匀，还算是一个不错的乘子吧。

9.png

接下来来看看我们本文的主角31了，31作为乘子算出的哈希值在第33分区有一定的小聚集。不过相比于数字17，主角31的表现又好了一些。首先是哈希值的聚集程度没有17那么严重，其次哈希值在其他区分布的情况也要好于17。总之，选31，准没错啊。

10.png

最后再来看看大质数101的表现，不难看出，质数101作为乘子时，算出的哈希值分布情况要好于主角31，有点喧宾夺主的意思。不过不可否认的是，质数101的作为乘子时，哈希值的分布性确实更加均匀。所以如果不在意质数101容易导致数据信息丢失问题，或许其是一个更好的选择。

遗留问题

接口 RandomAccess介绍

一个标记型接口，顺序、有下标的集合类实现了这个接口，就能用for(i=0,i<xx;i++)来通过下标遍历了。

条件：实现此接口的类得是随机访问，不能是顺序访问

附录

1. fail-fast和fail-safe介绍
2. 科普：为什么 String hashCode 方法选择数字31作为乘子
3. Why does Java's hashCode() in String use 31 as a multiplier?