java篇 常用工具类 0x01：Collection集合
文章目录
- 数据结构
- Collection 类族
- Collection 中的 List
- 手动实现 List 接口
- 用数组实现 List 接口
- 用引用实现 List 接口
- java 自带的 List 接口实现
- Collection 中的 Set
- Map
- HashMap
数据结构
数据结构是组织数据的方式。
程序 = 数据结构 + 算法
数组（Array）是一种最基本的数据结构。
计算机中的基础数据结构有：
- List 列表：ArrayList、LinkedList
- Set 集合：HashSet、TreeSet
- Queue 队列【先进先出】：通过 LinkedList 实现、PriorityQueue
- Map 映射【键值对】：HashMap、TreeMap、LinkedHashMap
stack 栈【后进先出】：由于java 的 stack 当初设计时有缺陷，所以不建议使用 stack，如果要使用栈这种数据结构，建议使用 LinkedList，它能实现栈的所有功能和方法。
高级数据结构有：
- Tree 树：通过 Java Collections Framework 实现
- Heap 堆
这些数据结构需要代码来实现。这些实现也是一个个的类，只是专注的问题更抽象和通用。
Collection 类族
package java.util;
import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public interface Collection<E> extends Iterable<E>{
xxxxx;
}
Collection 是一个接口（Iterable 的一个子接口），在 java.util 包中（而非 java.lang 包中），所以如果要使用，需要 import 导入进来使用。
Collection 接口的继承者（也是接口）和它们的实现构成了所谓的 Collection 类族。
Collection 集合里的元素是没有顺序的，和数组不太一样。集合里的元素虽然可以进行遍历，但并不能保证先放进去的元素会在遍历时先拿出来。
在 IDEA 中通过对 Collection 接口的继承关系查看（ctrl+H），可以看到它有哪些实现类以及子接口。常用的子接口有 List、Set。
在 IDEA 中查看 Collection 都有什么方法（菜单栏Navigate --> File Structure (ctrl+F12)）：
// 有注释的是 Collection 常用的方法
Collection
add(E):boolean <---------// 往集合中增加元素
addAll(Collection<? extends E>):boolean
clear():void
contains(Object):boolean <---------// 集合中是否有这个元素
containsAll(Collection<?>):boolean
isEmpty():boolean <---------// 集合是否为空
parallelStream():Stream<E>
remove(Object):boolean <---------// 从集合中移除元素
removeAll(Collection<?>):boolean
removelf(Predicate<? super E>):boolean
retainAll(Collection<?>):boolean
size():int <---------// 集合的大小
stream():Stream<E>
toArray():Object[]
toArray(T[]):T[]
继承自 Iterable 的方法
iterator():Iterator<E> <---------// 遍历
spliterator():Spliterator<E>
继承自 Object 的方法
equals(Object):boolean
hashCode():int
Collection 中的 List
List 是 Collection 的一个子接口。
List （链表）代表有顺序的一组元素。与 Collection 相比，List 又多了一些属性，比如说 Collection 是没有顺序的，而 List 是有顺序的。这意味着遍历 List 的时候也是有顺序的：先放进去的元素会先遍历到。
List 与数组虽然都是有顺序的，但与数组不同，数组创建后大小被确定了（只能放这么多元素），但 List 并不会。List 创建后的长度仍旧是可变的。
package java.util;
import java.util.function.UnaryOperator;
public interface List<E> extends Collection<E> {
xxxxx;
}
List 接口包含的方法
List
add(int, E):void <-------// 增加元素到指定下标
addAll(int, Collection<? extends E>):boolean
get(int):E <-------// 查看该下标对应的元素
indexOf(Object):int
lastIndexOf(Object):int
listIterator():ListIterator<E>
listIterator(int):ListIterator<E>
remove(int):E
replaceAll(UnaryOperator<E>):void
set(int, E):E
sort(Comparator<? super E>):void
subList(int, int):List<E>
继承自 Collection 的方法
add(E):boolean
addAll(Collection<? extends E>):boolean
clear():void
contains(Object):boolean
containsAll(Collection<?>):boolean
isEmpty():boolean
remove(Object):boolean
removeAll(Collection<?>):boolean
retainAll(Collection<?>):boolean
size():int
toArray():Object[]
toArray(T[]):T[]
iterator():Iterator<E>
spliterator():Spliterator<E>
equals(Object):boolean
hashCode():int
手动实现 List 接口
用数组实现 List 接口
尝试自己用数组来实现一遍 List 接口。
在 IDEA 中，implements List ，简单 alt+enter 一下，就得到如下代码，因为你要实现 List 接口，就得重写实现 List 接口中定义的所有抽象方法（非抽象方法可以重写也可以不管，直接继承）。
package collectiontest;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class MyArrayList implements List {
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public boolean contains(Object o) {
return false;
}
@Override
public Iterator iterator() {
return null;
}
@Override
public Object[] toArray() {
return new Object[0];
}
@Override
public boolean add(Object o) {
return false;
}
@Override
public boolean remove(Object o) {
return false;
}
@Override
public boolean addAll(Collection c) {
return false;
}
@Override
public boolean addAll(int index, Collection c) {
return false;
}
@Override
public void clear() {
}
@Override
public Object get(int index) {
return null;
}
@Override
public Object set(int index, Object element) {
return null;
}
@Override
public void add(int index, Object element) {
}
@Override
public Object remove(int index) {
return null;
}
@Override
public int indexOf(Object o) {
return 0;
}
@Override
public int lastIndexOf(Object o) {
return 0;
}
@Override
public ListIterator listIterator() {
return null;
}
@Override
public ListIterator listIterator(int index) {
return null;
}
@Override
public List subList(int fromIndex, int toIndex) {
return null;
}
@Override
public boolean retainAll(Collection c) {
return false;
}
@Override
public boolean removeAll(Collection c) {
return false;
}
@Override
public boolean containsAll(Collection c) {
return false;
}
@Override
public Object[] toArray(Object[] a) {
return new Object[0];
}
}
因为只是尝试自己手写实现（java其实已经有了更好的实现，后面会有介绍），所以现在只需要重点关注一些重要的抽象方法的实现，对于不那么重要的抽象方法的实现，直接 throw new UnsupportedOerationException() 表示异常（java自带的一个异常，表示没有此功能）即可（总比直接 InteliJ Idea 自动覆盖后什么都不做、调用该方法没有输出，要好一些）。
这次选择重点实现的方法为：size()、isEmpty()、contains()、clear()、get()、add()。
// 这个代码里的数组下标可能不太严谨有错误，但这里仅仅是展示如何通过数组来实现一个 List 接口而已，不用在意这些细节。
package collectiontest;
import java.util.*;
public class MyArrayList implements List {
private Object[] elements; // 用来实现 List 的数组
private int curr; // 数组下标
public MyArrayList() {
// 初始先创建一个 16 个元素的数组。
// 如果之后 List 要放入更多的元素，再重新创建一个更大的数组，把原来的 16 个元素复制进去，再往后添加新的元素即可。
elements = new Object[16];
curr = 0;
}
@Override
public int size() {
return curr;
}
@Override
public boolean isEmpty() {
return curr == 0;
}
// 遍历一遍其中元素，来确定链表中是否含有该元素。
@Override
public boolean contains(Object o) {
for (Object ele : elements) { // 事实上，这里不应该将 elements 数组都遍历，应该只遍历 curr 的长度
if (Objects.equals(ele, o)) {
return true;
}
}
return false;
}
// 将链表重置成空链表
@Override
public void clear() {
curr = 0;
}
@Override
public Object get(int index) {
if (index > curr || index < 0) {
throw new IndexOutOfBoundsException("out of bound " + curr + " for " + index);
}
return elements[index];
}
@Override
public boolean add(Object o) {
if (curr == elements.length - 1) {
Object[] elementsTemp = elements;
elements = new Object[elements.length * 2];
System.arraycopy(elementsTemp, 0, elements, 0, elementsTemp.length); // java 提供的数组拷贝方法，等效于下面注释部分的复制语句
// for (int i = 0; i < elementsTemp.length; i++) {
// elements[i] = elementsTemp[i];
// }
}
elements[curr] = o;
curr++;
return true; }
// 下面的方法都直接 throw new UnsupportedOperationException()，不一一去设计实现了。
@Override
public Iterator iterator() {
throw new UnsupportedOperationException();
}
@Override
public Object[] toArray() {
throw new UnsupportedOperationException();
}
@Override
public boolean remove(Object o) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(int index, Collection c) {
throw new UnsupportedOperationException();
}
@Override
public Object set(int index, Object element) {
throw new UnsupportedOperationException();
}
@Override
public void add(int index, Object element) {
throw new UnsupportedOperationException();
}
@Override
public Object remove(int index) {
throw new UnsupportedOperationException();
}
@Override
public int indexOf(Object o) {
throw new UnsupportedOperationException();
}
@Override
public int lastIndexOf(Object o) {
throw new UnsupportedOperationException();
}
@Override
public ListIterator listIterator() {
throw new UnsupportedOperationException();
}
@Override
public ListIterator listIterator(int index) {
throw new UnsupportedOperationException();
}
@Override
public List subList(int fromIndex, int toIndex) {
throw new UnsupportedOperationException();
}
@Override
public boolean retainAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public boolean removeAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public boolean containsAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public Object[] toArray(Object[] a) {
throw new UnsupportedOperationException();
}
}
虽然有很多方法没有去实现，但也已经可以发现，如果真的自己手动去实现一个 List 接口，是需要考虑很多细节的。
用引用实现 List 接口
尝试自己用引用来实现一遍 List 接口。
同样地，在 IDEA 中，implements List ，简单 alt+enter 一下，就得到要重写的代码的基本框架。因为你要实现 List 接口，就得重写实现 List 接口中定义的所有抽象方法（非抽象方法可以重写也可以不管，直接继承）。
因为只是尝试自己手写实现（java其实已经有了更好的实现，后面会有介绍），所以现在只需要重点关注一些重要的抽象方法的实现，对于不那么重要的抽象方法的实现，仍然直接 throw new UnsupportedOerationException() 表示异常（java自带的一个异常，表示没有此功能）即可（总比直接 InteliJ Idea 自动覆盖后什么都不做、调用该方法没有输出，要好一些）。
这次选择重点实现的方法仍为：size()、isEmpty()、contains()、clear()、get()、add()。
package collectiontest;
import java.util.*;
public class MyLinkedList implements List {
// 链表中的每个元素都有三个属性，一个是自身的值，一个是指向上一节点的引用，一个是指向下一节点的引用。
static class ListNode {
ListNode prev;
ListNode next;
Object value;
public ListNode(ListNode prev, ListNode next, Object value) {
this.prev = prev;
this.next = next;
this.value = value;
}
}
private ListNode start = null;
private ListNode tail = null;
private int size = 0;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
ListNode curr = start;
while (curr != null) {
if (Objects.equals(curr.value, o)) {
return true;
}
curr = curr.next;
}
return false;
}
@Override
public void clear() {
start = null;
tail = null;
size = 0;
}
@Override
public Object get(int index) {
// index从0开始算
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("out of bound " + size + " for " + index);
}
ListNode curr = start;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
// 遍历完后，curr 刚好指向第 index 位置的节点
return curr.value;
}
// 添加元素，只需要加到最后面（tail）即可，但要考虑链表为空的情况
@Override
public boolean add(Object o) {
// 创建一个新元素 newNode，让其 prev 属性指向原链表的最后一个元素
ListNode newNode = new ListNode(tail, null, o);
// 链表为空时，不但 tail 要变成 newNode，start 也要变成 newNode
if (start == null) {
start = newNode;
}
// 链表不为空时，之前的 tail.next 是 null，所以加入新元素前，把之前最后的元素的 next 属性指向新元素
if (tail != null) {
tail.next = newNode;
}
tail = newNode;
size++;
return true; }
@Override
public Iterator iterator() {
throw new UnsupportedOperationException();
}
@Override
public Object[] toArray() {
throw new UnsupportedOperationException();
}
@Override
public boolean remove(Object o) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(int index, Collection c) {
throw new UnsupportedOperationException();
}
@Override
public Object set(int index, Object element) {
throw new UnsupportedOperationException();
}
@Override
public void add(int index, Object element) {
throw new UnsupportedOperationException();
}
@Override
public Object remove(int index) {
throw new UnsupportedOperationException();
}
@Override
public int indexOf(Object o) {
throw new UnsupportedOperationException();
}
@Override
public int lastIndexOf(Object o) {
throw new UnsupportedOperationException();
}
@Override
public ListIterator listIterator() {
throw new UnsupportedOperationException();
}
@Override
public ListIterator listIterator(int index) {
throw new UnsupportedOperationException();
}
@Override
public List subList(int fromIndex, int toIndex) {
throw new UnsupportedOperationException();
}
@Override
public boolean retainAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public boolean removeAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public boolean containsAll(Collection c) {
throw new UnsupportedOperationException();
}
@Override
public Object[] toArray(Object[] a) {
throw new UnsupportedOperationException();
}
}
java 自带的 List 接口实现
之前已经手动实现过一次功能不太完整的 List 接口，可以发现实现一个完整的数据结构其实是挺复杂的，java 其实自带了 List 接口实现，可以直接拿来用，而无需自己去手动实现。
在 IDEA 中，查看 List 接口的继承关系，就可以看见 List 本身是有蛮多的实现的，其中最重要的两个实现是 ArrayList（java.util） 以及某些情况下也会用到的 LinkedList（java.util）。
若使用场景是频繁地根据一个索引来获取链表里的某个元素，则应该使用 ArrayList 而非 LinkedList，因为 LinkedList 必须每次从最开始的元素往下遍历去寻找到当前索引位置的元素，而 ArrayList 底层使用的是 Array，可以根据索引直接定位到该元素，而无需从头开始遍历。
而当链表中会存放大量的元素时，可以考虑使用 LinkedList，因为 ArrayList 每增加到一定大小时，会需要扩大数组的大小（而数组又是无法动态调整大小的），也就是说要重新创建一个更大的数组，然后还得把原来数组里的元素拷贝到新数组。当添加的元素很多时，屡次创建新数组会导致比较大的资源开销。而 LinkedList 没有这个问题，无论元素再多都只需要往末尾添加一个元素即可。
但一般情况下，都推荐使用 ArrayList。
下面尝试使用 java 自带的 List 接口实现，及之前自己手动实现的 List 接口。
package collectiontest;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
public class UseList {
public static void main(String[] args) {
printCollection(addElementsToCollection(new ArrayList()));
/*
输出class java.util.ArrayList中的元素，共10个
str0
str1
str2
str3
str4
str0
str1
str2
str3
str4
*/
printCollection(addElementsToCollection(new LinkedList()));
/*
输出class java.util.LinkedList中的元素，共10个
str0
str1
str2
str3
str4
str0
str1
str2
str3
str4
*/
printCollection(addElementsToCollection(new MyArrayList()));
/*
输出class collectiontest.MyArrayList中的元素，共10个
java.lang.UnsupportedOperationException
at collectiontest.MyArrayList.iterator(MyArrayList.java:73)
at collectiontest.UseList.printCollection(UseList.java:60)
at collectiontest.UseList.main(UseList.java:39)
*/
printCollection(addElementsToCollection(new MyLinkedList()));
/*
输出class collectiontest.MyLinkedList中的元素，共10个
java.lang.UnsupportedOperationException
at collectiontest.MyLinkedList.iterator(MyLinkedList.java:98)
at collectiontest.UseList.printCollection(UseList.java:60)
at collectiontest.UseList.main(UseList.java:40)
*/
// 此处报错是因为自己手动实现的 MyArrayList 与 MyLinkedList 并没有实现好 iterator 方法，直接 throw new UnsupportedOperationException 了
printList((List)addElementsToCollection(new ArrayList()));
/*
输出class java.util.ArrayList中的元素，共10个
str0
str1
str2
str3
str4
str0
str1
str2
str3
str4
*/
printList((List)addElementsToCollection(new MyArrayList()));
/*
输出class collectiontest.MyArrayList中的元素，共10个
str0
str1
str2
str3
str4
str0
str1
str2
str3
str4
*/
printList((List)addElementsToCollection(new MyLinkedList()));
/*
输出class collectiontest.MyLinkedList中的元素，共10个
str0
str1
str2
str3
str4
str0
str1
str2
str3
str4
*/
}
public static Collection addElementsToCollection(Collection collection) {
for (int i = 0; i < 10; i++) {
collection.add("str" + (i % 5));
}
return collection;
}
// 由于 Collection 是继承了 Iterable，所以可以使用 for-each（当然继承的是抽象方法，所以还是需要实现好该方法（iterator()）才不会报错）
public static void printCollection(Collection collection){
System.out.println();
System.out.println("输出"+collection.getClass()+"中的元素，共"+collection.size()+"个");
try{
for (Object element:collection){
System.out.println(element);
}
}catch (Exception ex){
ex.printStackTrace();
}
}
// 虽然自己手动实现的 List 接口也是继承自 Collection（也是Iterable的子接口），但是因为我们并没有实现好该抽象方法（iterator()），而是直接 throw new UnsupportedOperationException()，所以若使用for-each会报错
public static void printList(List list){
System.out.println();
System.out.println("输出"+list.getClass()+"中的元素，共"+list.size()+"个");
for(int i=0;i<list.size();i++){
System.out.println(list.get(i));
}
}
}
Collection 中的 Set
Set 代表一个元素不重复的集合。Set 中的元素两两不相等。
package java.util;
public interface Set<E> extends Collection<E> {
xxxxx;
}
java 中 Set 的最常用实现类是 HashSet。HashSet 使用了元素的 hash 值帮助去重。
[!warning] 与 List 不同，Set 与 Collection 一样，都是没有对顺序做要求的（只是接口不要求，但你可以去实现有顺序）。
package collectiontest;
import java.util.Collection;
import java.util.HashSet;
public class UseSet {
public static void main(String[] args) {
// printCollection(addElementsToCollection(new HashSet()));
HashSet a = new HashSet();
addElementsToCollection(a);
printCollection(a);
a.add("str5");
a.add("str6");
a.add("str7");
printCollection(a);
}
public static Collection addElementsToCollection(Collection collection) {
for (int i = 0; i < 10; i++) {
collection.add("str" + (i % 5));
}
return collection;
}
public static void printCollection(Collection collection){
System.out.println();
System.out.println("输出"+collection.getClass()+"中的元素，共"+collection.size()+"个");
try{
for (Object element:collection){
System.out.println(element);
}
}catch (Exception ex){
ex.printStackTrace();
}
}
}
// 运行结果：
/*
输出class java.util.HashSet中的元素，共5个
str3
str4
str1
str2
str0
输出class java.util.HashSet中的元素，共8个
str7
str5
str6
str3
str4
str1
str2
str0
Process finished with exit code 0
*/
// 可见 HashSet 元素是不重复的。
// 可见 HashSet 输出元素并不是依照元素加入顺序而定的。
而我们自己去实现 Set 时，不但要保证元素不重复（利用hashCode，并且一旦修改 hashCode()，就要相应修改 equals()，使得 equals() 返回 true 时（同样一个人），hashCode() 也得必须是 true（同样的名字）），还要让 Set 里的元素是不可变的。因为并没有一个机制是随时检查 Set 里面的元素是否相同，所以加入的时候虽然做了去重，但如果这个元素是可变的，那么后面它万一变成和另一个元素相等的值，那么就不符合 Set 的定义了。
- 当然也可以是让元素可变，但使用时约定用不可变的元素。（但这的确是不保险的）
Map
Map 和 List 一样，是一种最基础的数据结构，它描述的是一个 key 和一个 value 一一对应的数据结构。（所以这里也隐含了一个条件：包含的 key 是不能有重复的，而 value 倒可以相同）
与 List 不同，Map 并不是 Collection 的子接口。
每种高级语言都有对 Map 的定义和实现。
package java.util;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.io.Serializable;
public interface Map<K,V> { // K,V 分别代表 key 与 value 的类型
xxxxx;
}
Map 接口包含的方法
// 有注释的是 Map 常用的方法
Map
clear():void
compute(K,BiFunction<? super K, ? super V, ? extends V>):V
computeIfAbsent(K,Function<? super K, ? extends V>):V
computeIfPresent(K,BiFunction<? super K,? super V, ? extends V>):V
containsKey(Object):boolean <---------// 判断是否包含某个 key
containsValue(Object):boolean
entrySet():Set<Entry<K,V>>
forEach(BiConsumer<? super K, ? super V>):void
get(Object):V <---------// 查询：获取某个 key 对应的 value，注意这里的 key 没有使用 K 类型，而是使用了 Object 类型
getOrDefault(Object,V):V
isEmpty():boolean <---------// Map 是否为空
keySet():Set<K>
merge(K,V,BiFunction<? super V, ? super V, ? extends V>):V
put(K,V):V <---------// 增加：往 Map 中增加一个键值对
putAll(Map<? extends K, ? extends V>):void
putIfAbsent(K,V):V
remove(Object):V <---------// 删除：将某个键值对删除，注意这里的 key 没有使用 K 类型，而是使用了 Object 类型
remove(Object,Object):boolean
replace(K,V):V
replace(K,V,V):boolean
replaceAll(BiFunction<? super K, ? super V, ? extends V>):void
size():int <---------// Map 的大小
values():Collection<V>
// 继承自 Object 的方法
equals(Object):boolean
hashCode():int
// 内部接口
Entry
|
|---- comparingByKey():Comparator<Entry<K,V>>
|---- comparingByKey(Comparator<? super K>):Comparator<Entry<K,V>>
|---- comparingByValue():Comparator<Entry<K,V>>
|---- comparingByVlaue(Comparator<? super V>):Comparator<Entry<K,V>>
|---- getKey():K
|---- getValue():V
|---- setValue(V):V
|
|
|// 继承自 Object 的方法
|---- equals(Object):boolean
|---- hashCode():int
HashMap
java 中 Map 的最常用实现类是 HashMap。
HashSet 里面就是用到 HashMap 来实现的。
// HashSet 源码节选
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
xxxx;
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
xxxx;
}
// HashMap 源码节选
package java.util;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
import jdk.internal.access.SharedSecrets;
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
xxxxx;
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true); // 把 key 传给 hash()
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 不但用了 hashCode()，还做了个位运算（异或、无符号右移），主要是为了尽量避免哈希碰撞（两个不一样的对象但哈希值一样）
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) { // 主要是一个叫 table 的东西
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;
}
transient Node<K,V>[] table; // table 是个数组类型
/*
HashMap的工作方式：
通过一个对象（key）的哈希值，来决定这个对象在数组里面的位置。哈希值int模上数组长度就可以得到一个索引，再放到这个数组里面去。
这里的 Node 和 LinkList 的 node 差不多，再来一个 key 也是按照 key 算一个哈希值，然后看在数组的什么位置再放进去。如果发生哈希碰撞（两个对象的哈希值一样），甚至说，因为数组不会是无限大的，比如这个数组的size只有 10，往里面放第 11 个元素，再怎么模，也必定会有两个元素模完的值是一样的，就会发生冲突，这个时候，就会把后面的值，像链表一样接到前面一个值（取模后得到的值一样的哪个元素）的后面。所以 hashmap 是一个“数组+链表”的结构来实现的。当然实际上还会再复杂一些，比如说链表很长的时候会查询得比较慢，这个时候就会把链表变成树（树是一种比链表更复杂的数据结构，但搜索速度会比链表快很多）
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
return o instanceof Map.Entry<?, ?> e
&& Objects.equals(key, e.getKey())
&& Objects.equals(value, e.getValue());
}
}
xxxxx;
}
要实现一个很好的数据结构是很难的，里面要处理各种边界、条件判断等问题。这里只需要知道 hashmap 是用哈希值来决定数据的分布（数据放在什么地方）就可以了。
// HashMap 使用案例
import java.util.HashMap;
import java.util.Map;
public class MapTest {
public static void main(String[] args) {
Map<String, String> map = createMap(99);
// 通过 get 方法，得到传递的 key 的对应的 value
// 注意：get 方法并没有使用泛型，其类型为 Object
System.out.println(map.get("key20")); // 0.13932271661496198
/*
get 方法并没有使用泛型，而是让类型为 Object 的原因：
因为 key 实际上只需要 hashCode() 与 equals() 两个方法（只需要传递的这个对象的哈希值命中 key，就返回 value，否则返回 null），而这两个方法都是 Object 里的。
而虽然泛型也都必然是 Object 的子类，也就是说一定也有 equals() 和 hashCode() 方法，但若用泛型的 equals() 与 hashCode()，那么会多出一次类型转换的操作，另外类型不匹配是会引起 ClassCastException 报错。
*/
// 如果没有 key，或者 key 可能对应的值就是 null，那么就返回 null（这个也是不一定的，看具体map的实现，完全可以写一个map传入一个不存在的key时报错）
System.out.println(map.get(new Object())); // null
System.out.println(map.get("key999")); // null
// 注意：不是每种 map 的实现都允许 key 或者 value 为 null，使用时需要注意（hashpmap的确是允许的，但不代表其他map也允许）
map.put(null, "value of null key"); // 执行没有报错
map.put("testnull", null); // 执行没有报错
System.out.println("null key value:" + map.get(null)); // null key value:value of null key
System.out.println("null value support:" + map.get("testnull")); // null value support:null
// 删除 key
System.out.println("----------删除 key ----------");
String keyToRemove = "key9";
System.out.println(keyToRemove + "对应的值是：" + map.get(keyToRemove)); // key9对应的值是：0.4925088937549339
map.remove(keyToRemove);
System.out.println("执行删除操作后，" + keyToRemove + "对应的值是：" + map.get(keyToRemove)); // 执行删除操作后，key9对应的值是：null
System.out.println("----------遍历 key 和 value----------");
// 通过 Entry 类遍历 Map
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key为：" + entry.getKey() + ", value为：" + entry.getValue());
}
/*
一个键值对是一个 entry，entrySet 的 key 是不重复的，所以键值对也是不重复的，
entrySet 本身实现了 Iterable 接口，所以可以适用 forEach 来遍历。
entrySet() 返回的实际是一个 Set<Map.Entry<K, V>> 集合，其中元素类型为 Map.Entry<K, V>。
而 Map.Entry<K,V> 就是一对键值对，用 .getKey() 与 .getValue() 分别获取键值对的键与值。
*/
/*
输出：
key为：null, value为：value of null key
key为：key40, value为：0.4430242581425399
key为：key44, value为：0.8914849844362855
key为：key43, value为：0.8891786415633048
key为：key42, value为：0.2720485531626471
key为：key41, value为：0.23960919582037532
key为：key37, value为：0.1953736412489645
key为：key36, value为：0.0754359304871054
key为：key35, value为：0.38995257291562924
key为：key34, value为：0.268839799179147
key为：key39, value为：0.1839280220045867
...
可以看到是没有顺序的。
*/
System.out.println("----------遍历 value ----------");
// 只遍历 value
for (String value : map.values()){
System.out.println(value);
}
/*
输出：
value of null key
0.4430242581425399
0.8914849844362855
0.8891786415633048
0.2720485531626471
0.23960919582037532
0.1953736412489645
0.0754359304871054
0.38995257291562924
0.268839799179147
0.1839280220045867
...
倒是和上面的 value 顺序对应了
*/
System.out.println("----------遍历 key----------");
// 只遍历 key
for (String key : map.keySet()){
System.out.println(key);
}
/*
输出：
null
key40
key44
key43
key42
key41
key37
key36
key35
key34
key39
...
倒是和上面的 key 的顺序对应了
*/
// hashmap 的几个常用方法都要记一下：.entrySet()、.values()、.keySet()
}
// 创建 HashMap 实例，并按照泛型的定义，想里面放入 key 和 value
private static Map<String, String> createMap(int size) {
Map<String, String> ret = new HashMap<>();
for (int i = 0; i < size; i++) {
// put 的第一个为 key，第二个为 value
ret.put("key" + i, String.valueOf(Math.random()));
}
return ret;
}
}
HashMap 的几个常用方法都要记一下：
.entrySet() // 获取所有的键值对
.values() // 获取所有的值
.keySet() // 获取所有的 key
若用自己写的类作为 key，必须保证 .hashCode() 和 .equals() 方法都重写了（使 equals()返回为 true 则 hashCode() 返回也必须为 true），并且要保证这个类的对象的值一定是不可变的，因为如果作为 key 的对象是可变的，这个 HashMap 里面就乱套了（本来 key 是不重复的，但因为可变，可能导致有重复的 key）。