一、基本认知

1. 散列集

有一种众所周知的数据结构,可以快速地查找所需要的对象,这就是 散列表(hash table)。散列表为每个对象计算一个整数,称为 散列码(hash code) 。散列码是由对象的实例域产生的一个整数。更加准确的说,具有不同数据域的对象将产生不同的散列码。

1
2
3
4
5
6
7
8
9
10
11
12
13
// String类的hashCode 值
// s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char var[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

在 Java 中,散列表用链表数组实现。每个列表被称为桶(bucket)。要想查找表中对象的位置,就要先计算它的散列码,然后与桶的总数取余,所得到的结果就是保存这个元素的桶的索引。例如,如果某个对象的散列码为76268,并且有128个桶,对象应该保存在第108号桶中 (76268 除以 128 余 108)。如果桶中没有其他元素,此时就将元素直接插入到桶中就可以了。当然,有时候会遇到桶被占满的情况,这也是不可避免的。这种现象被称为 散列冲突(hash collision)

桶数 是指用于收集具有相同 散列值 的桶的数目。通常,将桶数设置为预计元素个数的 75% ~ 150%。标准类库使用的桶数是 2 的幂,默认值为16(为表大小提供的任何值都将被自动地转换为2的下一个幂)。

再散列(rehashed)如果散列表太满,负载达到负载因子的水平,就需要再散列。如果要对散列表再散列,就需要创建一个桶数更多的表,并将所有元素插入新表中,然后丢弃原来的表。

尺寸 表中当前存储的位数

负载因子 尺寸/容量(桶数),空表负载为0,满表负载为1.0,负载轻产生的冲突可能性小,有利于插入和查询,默认的负载因子为0.75;

2. 队列(queue)

队列接口指出可以在队列的尾部添加元素,在队列的头部删除元素,并且可以查找队列中元素的个数。当需要收集对象,并按照“先进先出”的规则检索对象时就应该使用队列。

3. HashMap

存在的问题:死链问题及扩容数据丢失问题。

二、接口源码

java.util.Collection 1.2
  • Iterator iterator()

    返回一个用于访问集合中每个元素的迭代器。

  • int size()

    返回当前存储在集合中的元素个数。

  • boolean isEmpty()

    如果集合中没有元素,返回true.

  • boolean contains(Object obj)

    如果这个集合包含other 集合中的所有元素,返回true。

  • boolean add(Object element)

    将一个元素添加到集合中。如果由于这个调用改变了集合,返回true。

  • boolean addAll(Collection<? extends E> other)

    将other 集合中的所有元素添加到这个集合中。如果由于这个调用改变了集合,返回true。

  • boolean remove(Object obj)

    从这个集合中删除等于obj 的对象。如果有匹配的对象被删除,返回true。

  • boolean removeAll(Collection<?> other)

    从这个集合中删除other 集合中存在的所有元素。如果由于这个调用改变了集合,返回true。

  • void clear()

    从这个集合中删除所有的元素

  • boolean retainAll(Collection<?> other)

    从这个集合中删除所有与other 集合中的元素不同的元素。如果由于这个调用改变了集合,返回true。

  • Object[] toArray()

    返回这个集合的对象数组

  • T[] toArray(T[] arrayToFill)

    返回这个集合的对象数组。如果arrayToFill 足够大,就将集合中的元素填入这个数组中。剩余空间填补null;否则,分配一个新数组,其成员类型与 arrayToFill 的成员类型相同,其长度等于集合的大小,并添入集合元素。

java.util.Iterator 1.2
  • boolean hasNext()

    如果存在可访问的元素,返回true。

  • E next()

    返回将要访问的下一个对象。如果已经到达了集合的尾部,将抛出一个NoSuchElementException。

  • void remove()

    删除上次访问的对象。这个方法必须紧跟在访问一个元素之后执行。如果上次访问之后,集合已经发生了变化,这个方法将抛出一个IllegalStateException。

java.util.List 1.2
  • ListIterator listIterator()

    返回一个列表迭代器,以便用来访问列表中的元素。

  • ListIterator listIterator(int index)

    返回一个列表迭代器,以便用来访问列表中的元素,这个元素是第一次调用next 返回的给定索引的元素。

  • void add(int i, E element)

    在给定位置添加一个元素。

  • void addAll(int i, Collection<? extends E> elements)

    将某个集合中的所有元素添加到给定位置。

  • E remove(int i)

    删除给定位置的元素并返回这个元素。

  • E get(int i)

    获取给定位置的元素。

  • E set(int i, E element)

    用新元素取代给定位置的元素,并返回原来的这个元素。

  • int indexof(Object element)

    返回与指定元素相等的元素在列表中第一次出现的位置,如果没有这样的元素将返回-1。

  • int lastIndexOf(Object element)

    返回与指定元素相等的元素在列表中最后一次出现的位置,如果没有这样的元素将返回-1。

java.util.ListIterator 1.2
  • void add(E newElement)

    在当前位置添加一个元素。

  • void set(E newElement)

    用新元素取代next 或 previous 上次访问的元素。如果在next 或 previous 上次调用之后列表结构被修改了,将抛出一个 IllegalStateException 异常。

  • boolean hasPrevious()

    当反向迭代列表时,还有可供访问的元素,返回true。

  • E previous()

    返回前一个对象。如果已经到达了列表的头部,就抛出一个NoSuchElementException 异常

  • int nexIndex()

    返回下一次调用next 方法时将返回的元素索引。

  • int previousIndex()

    返回下一次调用previous 方法时将返回的元素索引。

java.util.LinkedList 1.2
  • LinkedList()

    构造一个空链表。

  • LinkedList(Collection<? extends E> elements)

    构造一个链表,并将集合中的所有的元素添加到这个链表中。

  • void addFirst(E element)

  • void addLast(E element)

    将某个元素添加到列表的头部或尾部

  • E getFirst()

  • E getLast()

    返回列表头部或尾部的元素

  • E removeFirst()

  • E removeLast()

    删除并返回列表头部或尾部的元素。

java.util.HashSet 1.2
  • HashSet()

    构造一个空散列表。

  • HashSet(Collection<? extend E> elements)

    构造一个散列集,并将集合中的所有元素添加到这个散列集中。

  • HashSet(int initialCapacity)

    构造一个空的具有指定容量(桶数) 的散列集

  • HashSet(int initialCapacity, float loadFactor)

    构造一个具有指定容量和装填因子(一个 0.0 ~ 1.0 之间的数值,确定散列表填充的百分比,当大于这个百分比时,散列表进行再散列)的空散列集。

java.lang.Object 1.0
  • int hashCode()

    返回这个对象的散列码。散列码可以是任何整数,包括正数或负数。equals 和 hashCode 的定义必须兼容,既如果 x.equals(y),x.hashCode 必须等于y.hashCode()。

java.util.TreeSet 1.2
  • TreeSet()

    构造一个空树集。

  • TreeSet(Collection<? extends E> elements)

    构造一个树集,并将集合中的所有元素添加到树集中。

java.lang.Comparable 1.2
  • int compareTo(T other)

    将这个对象(this)与另一个对象(other)进行比较,如果this 位于 other 之前则返回负值;如果两个对象在排列顺序中处于相同的位置则返回0;如果this 位于 other 之后则返回正值。

java.util.Comparator 1.2
  • int compare(T a, T b)

    将两个对象进行比较,如果 a 位于 b 之前则返回负值;如果两个对象在排列顺序中处于相同的位置则返回0 ;如果 a 位于 b 之后 则返回正值。

java.util.SortedSet 1.2
  • Comparator<? super E> comparator()

    返回用于对元素进行排序的比较器。如果元素用 Comparable 接口的 compareTo 方法进行比较则返回 null。

  • E first()

  • E last()

    返回有序集中的最小元素或最大元素。

java.util.NavigableSet 6
  • E higher(E value)

  • E lower(E value)

    返回大于value 的最小元素或小于value 的最大元素,如果没有这样的元素则返回null。

  • E ceiling(E value)

  • E floor(E value)

    返回大于等于 value 的最小元素或小于等于 value 的最大元素,如果没有这样的元素则返回 null。

  • E pollFirst()

  • E pollLast()

    删除并返回这个集合中的最大元素或最小元素,这个集为空时返回 null。

  • Iterator descendingIterator()

    返回一个按照递减顺序遍历集中元素的迭代器。

java.util.TreeSet
  • TreeSet()

    构造一个用于排序 Comparable 对象的树集。

  • TreeSet(Comparator<? super E> c)

    构造一个树集,并使用指定的比较器对其中的元素进行排序。

  • TreeSet(SortedSet<? extends E> elements)

    构造一个树集,将有序集中的所有元素添加到这个树集中,并使用与给定集相同的元素比较器。

java.util.Queue 5.0
  • boolean add(E element)

  • boolean offer(E element)

    如果队列没有满,将给定的元素添加到这个双端队列的尾部并返回 true。如果队列满了,第一个方法将抛出一个 IllegalStateException,而第二个方法返回 false。

  • E remove()

  • E poll()

    假如队列不空,删除并返回这个队列头部的元素。如果队列是空的,第一个方法抛出NoSuchElementException,而第二个方法返回 null。

  • E element()

  • E peek()

    如果队列不空,返回这个队列头部的元素,但不删除。如果队列空,第一个方法将抛出一个NoSuchElementException, 而第二个方法返回 null。

java.util.Deque 6 双端队列
  • void addFirst(E element)

  • void addLast(E element)

  • boolean offerFirst(E element)

  • boolean offerLast(E element)

    将给定的对象添加到双端队列的头部或尾部。如果队列满了,前面两个方法将抛出一个IllegalStateException,而后面两个方法返回 false。

  • E removeFirst()

  • E removeLast()

  • E pollFirst()

  • E pollLast()

    如果队列不空,删除并返回队列头部的元素。如果队列为空,前面两个方法将抛出一个NoSuchElementException,而后面两个方法返回 null。

  • E getFirst()

  • E getLast()

  • E peekFirst()

  • E peekLast()

    如果队列非空,返回队列头部的元素,但不删除。如果队列空,前面两个方法将抛出一个 NoSuchElementException,而后面两个方法返回 null。

java.util.ArrayDeque 6
  • ArrayDeque()

  • ArrayDeque(int initialCapacity)

    用初始容量16 或给定的初始容量构造一个无限双端队列。

java.util.PriorityQueue 5.0 优先级队列
  • PriorityQueue()

  • PriorityQueue(int initialCapactiy)

    构造一个用于存放Comparable 对象的优先级队列。

  • PriorityQueue(int initialCapactiy, Comparator<? super E> c)

    构造一个优先级队列,并用指定的比较器对元素进行排序。

java.util.Map<K, V> 1.2
  • V get(object key)

    获取与键对应的值;返回与键对应的对象,如果在映射表中没有这个对象则返回 null。键可以为 null。

  • V put(K key, V value)

    将键与对应的值关系插入到映射表中。如果这个键已经存在,新的对象将取代与这个键对应的旧对象。这个方法将返回键对应的旧值。如果这个键以前没有出现过则返回null。键可以为null,但值不能为null。

  • void putAll(Map<? extend K,? extends V> entries)

    将给定映射表中的所有条目添加到这个映射表中。

  • boolean containsKey(Object key)

    如果在映射表中已经有这个值,返回true。

  • boolean containsValue(Object value)

    如果映射表中已经有这个值,返回true

  • Set<Map.Entry<K, V>> entrySet()

    返回Map.Entry 对象的集视图,即映射表中的 键/ 值 对。可以从这个集中删除元素,同时也从映射表中删除了它们。但是,不能添加任何元素。

  • Set keySet()

    返回映射表中所有键的集视图。可以从这个集中删除元素,同时也从映射表中删除了它们。但是,不能添加任何元素。

  • Collection values()

    返回映射表中所有值的集合视图。可以从这个集中删除元素,同时也从映射表中删除了它们。但是,不能添加任何元素。

  • Collection values()

    返回映射表中所有值的集合视图。可以从这个集中删除元素,同时也从映射表中删除了它们。但是,不能添加任何元素。

java.util.Map.Entry<K,V> 1.2
  • K getKey()

  • V getValue()

    返回这个条目的键或值。

  • V setValue(V newValue)

    设置在映射表中与新值对应的值,并返回旧值。

java.util.HashMap<K, V> 1.2
  • HashMap()

  • HashMap(int initialCapacity)

  • HashMap(int initialCapacity, float loadFactor)

    用给定的容量和装填因子构造一个空散列映射表(装填因子是一个 0.0 ~ 1.0 之间的数值。 这个数值决定散列表填充的百分比。一旦到了这个比例,就要将其再散列到更大的表中)。默认的装填因子是 0.75。

java.util.TreeMap<K, V> 1.2
  • TreeMap(Comparator<? super K> c)

    构造一个树映射表,并使用一个指定的比较器对键进行排序。

  • TreeMap(Map<? extends K, ? extends V> entries)

    构造一个树映射表,并将某个映射表中的所有条目添加到树映射表中。

  • TreeMap(SortedMap<? extends K, ? extend V> entries)

    构造一个树映射表,将某个有序映射表中的所有条目添加到树映射表中,并使用与给定的有序映射表相同的比较器。

java.util.SortedMap<K, V> 1.2
  • Comparator<? super K> comparator()

    返回对键进行排序的比较器。如果键是用Comparable接口的 compareTo 方法进行比较的,返回null。

  • K firstKey()

  • K lastKey()

    返回映射表中最小元素和最大元素。

java.util.WeakHashMap<K, V> 1.2
  • WeakHashMap()

  • WeakHashMap(int initialCapacity)

  • WeakHashMap(int initialCapacity, float loadFactor)

    用给定的容量和填充因子构造一个空的散列映射表

java.util.LinkedHashSet 1.4
  • LinkedHashSet()

  • LinkedHashSet(int initialCapacity)

  • LinkedHashSet(int initicalCapacity, float loadFactor)

    用给定的容量和填充因子构造一个空链接散列表

java.util.LinkedHashMap<K, V> 1.4
  • LinkedHashMap()

  • LinkedHashMap(int initialCapacity)

  • LinkedHashMap(int initialCapacity, float loadFactor)

  • LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

    用给定的容量、填充因子和顺序构造一个空的链接散列映射表。

  • protected boolean removeEldestEntry(Map.Entry<K, V> eldest)

    如果想删除 eldest 元素,并同时返回true, 就应该覆盖这个方法。eldest 参数是预期要删除的条目。这个方法将在条目添加到映射表中之后调用。其默认的实现将返回 false。即在默认情况下,旧元素没有被删除。然而,可以重新定义这个方法,以便有选择地返回 true。假如,如果最旧的条目符合一个条件,或者映射表超过了一定大小,则返回 true。

java.util.EnumSet<E extends Enum> 5.0
  • static <E extends Enums> EnumSet allOf(Class enumType)

    返回一个包含给定枚举类型的所有值的集。

  • static <E extends Enum> EnumSet noneOf(Class enumType)

    返回一个空集,并有足够的空间保存给定的枚举类型的所有的值。

  • static <E extends Enum> EnumSet range(E from, E to)

    返回一个包含from ~ to 之间的所有值(包含两个边界元素) 的集

  • static <E extends Enum> EnumSet of(E value)

  • static <E extends Enum> EnumSet of(E value, E … values)

    返回包括给定值的集。

java.util.EnumMap<K extends Enum, V> 5.0
  • EnumMap(Class keyType)

    构造一个键为给定类型的空映射集。

java.util.IdentityHashMap<K, V> 1.4 标识散列映射表
  • IdentityHashMap()

  • IdentityHashMap(int expectedMaxSize)

    构造一个空的标识散列映射集,其容量是大于 1.5 * expectedMaxSize 的2的 最小次幂(expectedMaxSize 的默认值是21)。

java.lang.IdentityHashMap<K, V> 1.4
  • static int identityHashCode(Object obj) 1.1

    返回Object.hashCode 计算出来的相同的散列码(根据对象的内存地址产生),即使obj 所属的类已经重新定义了 hashCode 方法也是如此。

java.util.RandomAccess
  • 没有任何方法,用来检测一个特定的集合是否支持高效的随机访问。ArrayList 类 和 Vector 类都实现了 RandomAccess 接口。 if (c instanceof RandomAccess) {} else {}。

三、友情链接

科普:为什么 String hashCode 方法选择数字31作为乘子

jdk1.8 HashMap源码分析