Java - 集合概述

集合概述

Java 集合概览

Java 集合, 也称为 容器, 主要是由两大接口派生而来 :

• Collection : 主要用于存放单一元素
• Map : 主要用于存放键值对

对于 Collection 接口, 下面又有三个主要的子接口 :

• List
• Set
• Queue

Java 集合框架关系图

小贴士

图中只列举了主要的继承派生关系, 并没有列举所有关系

List, Set, Queue, Map 四者的区别

List

• 存储的元素是有序的, 可重复的
• 是对付顺序的好帮手

Set

• 存储的元素是无序的, 不可重复的
• 注重独一无二的性质

Queue

• 按特定的排队规则来确定先后顺序
• 存储的元素是有序的, 可重复的
• 实现排队功能的叫号机

Map

• 使用键值对 (key-value) 存储
• key 是无序的, 不可重复的, value 是无序的, 可重复的
• 每个键最多映射到一个值
• 用 key 来搜索的专家

集合框架底层数据结构总结

List

• ArrayList : Object[] 数组
• Vector : Object[] 数组
• LinkedList : 双向链表
  • JDK 1.6 之前为循环链表
  • JDK 1.7 取消了循环

Set

• HashSet (无序, 唯一) : 基于 HashMap 实现, 底层采用 HashMap 存储元素
• LinkedHashSet : LinkedHashSet 是 HashSet 的子类, 并且其内部是通过 LinkedHashMap 来实现的
• TreeSet (有序, 唯一) : 红黑树 (自平衡的排序二叉树)

Queue

• PriorityQueue : Object[] 数组来实现二叉堆
• ArrayQueue : Object 数组 + 双指针

Map

• HashMap :
  • JDK 1.8 之前由 数组 + 链表 组成, 数组是 HashMap 的主体, 链表则是主要为了解决哈希冲突二存在的 (拉链法)
  • JDK 1.8 由 数组 + 链表 / 红黑树 组成. 当链表长度大于阙值 (默认为 8) 且数组长度大于等于 64, 会将链表转换为红黑树, 减少搜索时间 (如果数组长度小于 64, 则进行数组扩容操作而非将链表转为红黑树)
• LinkedHashMap : LinkedHashMap 继承自 HashMap, 底层数据结构由 数组 + 链表 / 红黑树 + 双向链表 组成. 双向链表使得 LinkedHashMap 在 HashMap 的结构上 可以保持插入键值对的顺序, 同时通过对链表进行对应的操作, 实现了 访问顺序相关逻辑
• Hashtable : 数组 + 链表组成的, 数组是 Hashtable 的主体, 链表则是主要为了解决哈希冲突存在的
• TreeMap : 红黑树 (自平衡的排序二叉树)

Collection - List

ArrayList 和 Vector 的区别

• ArrayList 是 List 的 主要实现类, 底层使用 Object[] 数组, 适用于频繁的查找工作, 线程不安全
• Vector 是List 的 古老实现类, 底层使用 Object[] 数组, 线程安全

小贴士

即使在需要保障线程安全的场景下, 也不推荐使用 Vector, 也不推荐使用 Collections 工具类里的 synchronizedXxx () 方法, 而是使用 JUC 包下的并发集合

ArrayList 和 LinkedList 的区别

• 线程是否安全 :
  • ArrayList 是不同步的, 不保证线程安全
  • LinkedList 是不同步的, 不保证线程安全
• 底层数据机构 :
  • ArrayList 底层采用 Object[] 数组
  • LinkedList 底层采用 双向链表
    • JDK 1.6 之前为循环链表
    • JDK 1.7 取消了循环
• 插入和删除是否受元素位置的影响 :
  • xxxxxxxxxx2 1Integer[] array = {1, 2, 3};2List list = List.of(array);java
    • 执行 add (E e) 的时候, ArrayList 会默认将该元素添加到此列表的末尾, 这种情况的时间复杂度就是 O (1)
    • 执行 add (int index, E e) 的时候, ArrayList 会将该元素添加到指定位置 index, 这种情况的时间复杂度就是 O (n - index)
  • LinkedList 采用链表存储, 所以, 如果是在头尾插入和删除元素的时间复杂度不收元素位置的影响, 但如果是要在指定位置 index 插入和删除元素的话, 时间复杂度近似为 O (n), 因为需要先移动到指定位置再插入
    • add(E e), addFirst (E e), addLast (E e), removeFirst (E e), removeLast (E e), 这些情况时间复杂度近似 O (1)
    • add (int index, E e), remove (int index), 这些情况时间复杂度近似 O (n)
• 是否支持快速随机访问 : 快速随机访问就是通过元素的序号快速获取到元素对象 (对应于 get (int index) 方法)
  • ArrayList 支持
  • LinkedList 不支持
• 内存空间占用 :
  • ArrayList 的空间浪费主要体现在 List 列表的末尾会预留一定的熔炼空间
  • LinkedList 的空间花费主要体现在它的每一个元素都需要消耗比 ArrayList 更多的空间 (因为要存放直接后继和直接前驱及数据)

双向链表和双向循环链表

双向链表

双向链表 : 包含两个指针, 一个 prev 指向前一个节点, 一个 next 指向后一个节点

双向循环链表

双向循环链表 : 最后一个节点的 next 指向 head, 而 head 的 prev 指向最后一个节点, 构成一个环

详细介绍

看图轻松理解数据结构与算法系列 (双向链表) (opens new window)

RandomAccess 接口

源码

public interface RandomAccess {
}

RandomAccess 接口中什么都没有定义, 在我看来, RandomAccess 接口仅起一个标识的作用, 标识实现这个接口的类具有随机访问的功能

例子

在 Collections 类的 binarySearch () 方法中, 它要判断传入的 List 是否是 RandomAccess 的实例, 如果是, 调用 indexedBinarySearch () 方法, 如果不是, 调用 iteratorBinarySearch () 方法

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现的原因

与底层数据结构有关.

ArrayList 底层是数组, 数组天然支持随机访问, 时间复杂度为 O (1), 所以称为快速随机访问, 而 LinkedList 底层是链表, 链表需要遍历到特定位置才能访问特定位置的元素, 时间复杂度为 O (n), 所以不支持快速随机访问.

RandomAccess 接口只是标识, 并非是因为 ArrayList 实现了 RandomAccess 接口才具有快速随机访问功能的, 而是因为 ArrayList 具有快速随机访问功能才会去实现 RandomAccess 接口

Collection - Set

Comparable 和 Comparator 的区别

• Comparable 接口实际上是出自 java.lang 包下, 它有一个 compareTo (Object obj) 方法用来排序, 也称为 自然排序
• Comparator 接口实际上是出自 java.util 包下, 它有一个 compare (Object obj1, Object obj2) 方法用来排序, 也称为 定制排序

一般我们需要对应集合使用自定义排序的时候, 我们就要重写 compareTo () 方法或 compare () 方法

当我们需要对某一集合实现两种排序方式, 比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话, 我们可以重写 compareTo () 方法和使用自制的 Comparator 方法或者以两个 Comparator 来实现歌名排序和歌星名排序, 第二种代码我们只能用两个参数版的 Collections.sort ()

Comparator 定制排序

代码

    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    arrayList.add(-1);
    arrayList.add(3);
    arrayList.add(3);
    arrayList.add(-5);
    arrayList.add(7);
    arrayList.add(4);
    arrayList.add(-9);
    arrayList.add(-7);

    System.out.println("原始数组:");
    System.out.println(arrayList);

    // void reverse(List list)：反转
	Collections.reverse(arrayList);
	System.out.println("Collections.reverse(arrayList):");
	System.out.println(arrayList);

	// void sort(List list),按自然排序的升序排序
	Collections.sort(arrayList);
	System.out.println("Collections.sort(arrayList):");
	System.out.println(arrayList);

	// 定制排序的用法
	Collections.sort(arrayList, new Comparator<Integer>() {

		@Override
		public int compare(Integer o1, Integer o2) {
			return o2.compareTo(o1);
		}
	});
	System.out.println("定制排序后：");
	System.out.println(arrayList);

输出

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

重写 compareTo 方法实现按年龄来排序

代码

/** 
 * person 对象没有实现 Comparable 接口, 所以必须实现, 这样才不会出错, 才可以使 treemap 中的数据按顺序排列
 *  前面一个例子的 String 类已经默认实现了 Comparable 接口, 详细可以查看 String 类的 API 文档, 另外其他
 *  像 Integer 类等都已经实现了 Comparable 接口, 所以不需要另外实现了
 */
public  class Person implements Comparable<Person> {
    
    private String name;
    private int age;

    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    /**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}

测试代码

public static void main(String[] args) {
	TreeMap<Person, String> pdata = new TreeMap<Person, String>();
	pdata.put(new Person("张三", 30), "zhangsan");
	pdata.put(new Person("李四", 20), "lisi");
	pdata.put(new Person("王五", 10), "wangwu");
	pdata.put(new Person("小红", 5), "xiaohong");
    
	// 得到key的值的同时得到key所对应的值
	Set<Person> keys = pdata.keySet();
	for (Person key : keys) {
		System.out.println(key.getAge() + "-" + key.getName());
	}
}

输出

5-小红
10-王五
20-李四
30-张三

无序性和不可重复性的含义是什么

1. 什么是 无序性 ? : 无序性不等于随机性, 无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加, 而是根据数据的哈希值决定的
2. 什么是 不可重复性 ? : 不可重复性是指添加的元素按照 equals () 判断时, 返回 false, 同时需要重写 equals () 方法和 HashCode () 方法

比较 HashSet, LinkedHashSet, TreeSet 三者的异同

• HashSet, LinkedHashSet, TreeSet 都是 Set 接口的实现类, 都能保证元素唯一, 并且都不是线程安全的
• HashSet, LinkedHashSet, TreeSet 的主要区别在于底层数据结构不同
  • HashSet 底层数据结构是 哈希表, 基于 HashMap 实现
  • LinkedHashSet 底层数据结构是 哈希表 + 链表, 元素的插入和取出顺序满足 FIFO
  • TreeSet 底层数据结构是 红黑树, 元素是有序的, 排序的方式有自然排序和定制排序
• 三者的应用场景不同
  • HashSet 用于 不需要保证元素插入和取出顺序的场景
  • LinkedHashSet 用于 保证元素的插入和取出顺序满足 FIFO 的场景
  • TreeSet 用于 支持元素自定义排序规则的场景

Collection - Queue

Queue 和 Deque 的区别

Queue 是 单端队列, 只能从一端插入元素, 从另一端删除元素, 实现上一般遵循 先入先出 (FIFO) 规则

Queue 扩展了 Collection 的接口, 根据 因为容量问题而导致操作失败后处理方式的不同, 可以分为两类方法 :

• 操作失败后会抛出异常
• 操作失败后会返回特殊值

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque 是 双端队列, 在队列的两段均可以插入或删除元素

Deque 扩展了 Queue 的接口, 增加了再队首和队尾进行插入和删除的方法, 同样根据失败后处理方式的不同分为两类

Deque 接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

事实上, Deque 还提供有 push () 和 pop () 等其他方法, 可用于模拟栈

ArrayDeque 和 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口, 两者都具有队列的功能

• 底层数据结构不同 :
  • ArrayDeque 是 基于可变长的数组和双指针来实现
  • LinkedList 是 通过链表来实现
• 是否支持存储 NULL 数据 :
  • ArrayDeque 不支持存储 NULL 数据
  • LinkedList 支持存储 NULL 数据
• 引入时间不同 :
  • ArrayDeque 在 JDK 1.6 被引入
  • LinkedList 在 JDK 1.2 被引入
• 扩容机制不同 :
  • ArrayDeque 插入时可能存在扩容过程, 不过均摊后插入操作时间复杂度依然为 O (1)
  • LinkedList 不需要扩容, 但是每次插入时均需要申请新的堆空间, 均摊新能更慢
• 是否能模拟栈 :
  • ArrayDeque 可以实现栈
  • LinkedList 不能实现栈
• 性能 : ArrayDeque 要比 LinkedList 更好

PriorityQueue

PriorityQueue 是在 JDK 1.5 中被引入的, 其与 Queue 的区别在于 元素的出队顺序是与优先级相关的, 即 总是优先级最高的元素先出队

• PriorityQueue 利用了 二叉堆 的数据结构来实现, 底层使用 可变长的数组 来存储数据
• PriorityQueue 通过 堆元素的上浮和下沉, 实现了在 O (logn) 的时间复杂度内插入和删除堆顶元素
• PriorityQueue 是 非线程安全的, 且 不支持存储 NULL 和 non-comparable 的对象
• PriorityQueue 默认是 小顶堆, 但可以接收一个 Comparator 作为构造参数, 从而来自定义元素优先级的先后

Map 接口

HashMap 和 Hashtable 的区别

• 线程是否安全 :
  • HashMap 是 非线程安全的
  • Hashtable 是 线程安全的, 因为 Hashtable 内部的方法基本都经过 synchronize 修饰
• 效率 :HashMap 的效率比 Hashtable 高
• 对 null key 和 null value 的支持 :
  • HashMap 可以存储 null key 和 null value, 但是 **null 作为键只能有一个, null 作为值可以有多个**
  • Hashtable 不允许有 null 键和 null 值, 否则会抛出 NPE (NullPointerException)
• 初始容量大小和每次扩容容量大小的不同 :
  • HashMap
    • 创建时如果不指定容量初始值, 则默认大小为 16. 之后每次扩容, 容量变为原来的 2 倍.
    • 创建时如果给定了容量初始值, 则 HashMap 会将其扩充为 2 的幂次方大小 (HashMap 的 tableSizeFor () 方法保证). 也就是说, HashMap 总是使用 2 的幂作为哈希表的大小
  • Hashtable
    • 创建时如果不指定容量初始值, 则默认大小为 11. 之后每次扩容, 容量变为原来的 2n + 1.
    • 创建时如果给定了容量初始值, 则 Hashtable 会直接使用你给定的初始值.
• 底层数据结构 :
  • HashMap
    • JDK 1.8 之前, HashMap 底层数据结构是 数组 + 链表
    • JDK 1.8 , HashMap 底层数据结构是 数组 + 链表 / 红黑树
  • Hashtable 底层数据结构是 数组 + 链表

HashMap 中带有初始容量的构造函数

public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: " +
										   initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: " +
										   loadFactor);
	this.loadFactor = loadFactor;
	this.threshold = tableSizeFor(initialCapacity);
}


public HashMap(int initialCapacity) {
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

tableSizeFor () 方法 (用于保证 HashMap 总是使用 2 的幂作为哈希表的大小

static final int tableSizeFor(int cap) {
	int n = cap - 1;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashMap 和 HashSet 的区别

HashSet 的底层就是基于HashMap 实现的

HashSet 的源码非常少, 除了 clone (), writeObject (), readObject () 是 HashSet 自己不得不实现之外, 其他方法都是直接调用 HashMap 中的方法

• 实现接口不同 :
  • HashMap 实现了 Map 接口
  • HashSet 实现了 Set 接口
• 存储元素格式不同 :
  • HashMap 存储 键值对
  • HashSet 存储 对象
• 添加元素方式不同 :
  • HashMap 通过调用 put () 添加数据
  • HashSet 通过调用 add () 添加数据. 数据添加成功则返回 true, 数据添加失败则返回 false
• 计算 hashcode 方式不同 :
  • HashMap 使用 key 计算 hashcode
  • HashSet 使用成员对象来计算 hashcode

HashMap 和 TreeMap 的区别

TreeMap 和 HashMap 都继承自 AbstractMap, 但 TreeMap 还实现了 NavigableMap 接口和 SortedMap 接口

实现 NavigableMap 接口让 TreeMap 有了 对集合内元素的搜索的能力

实现 SortedMap 接口让 TreeMap 有了 对集合内的元素根据键排序的能力. 默认是按 key 的升序排序, 也可以指定排序的比较器

例子

public class Person {
    
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }


    public static void main(String[] args) {
        // 实现方式一 : 匿名内部类
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        // 实现方式二 : Lambda
        TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  			int num = person1.getAge() - person2.getAge();
  			return Integer.compare(num, 0);
		});
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

输出

person1
person4
person2
person3

可以看出, TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了

综上, 相比于 HashMap 来说, TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内部元素的搜索的能力

HashSet 如何查重

当你把对象加入 HashSet 时, HashSet 会 先计算对象的 hashcode 值来判断对象加入的位置, 同时也会与其他加入的对象的 hashcode 值作比较, 如果没有相符的 hashcode, HashSet 会假设对象没有重复出现. 但是如果发现有相同的 hashcode 值的对象, 这时会调用 equals () 方法来检查 hashcode 相等的对象是否真的相同. 如果两者相同, HashSet 就不会让加入操作成功

HashSet 的 add () 方法

// 返回值 : true if this set did not already contain the specified element
// 返回值 : 当set中没有包含add的元素时返回真
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

HashMap 的 putVal () 方法

// 返回值 : previous value, or null if none
// 返回值 ： 如果插入位置没有元素返回null，否则返回上一个元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
}

也就是说实际上, 无论 HashSet 中是否已经存在了某元素, HashSet 都会直接插入, 只是会在 add () 方法的返回值中告诉我们插入前是否存在相同元素

hashCode () 方法和 equals () 方法的相关规定

1. 如果两个对象相等, 则 hashcode 一定也是相同的
2. 如果两个对象相等, 则 equals () 方法返回 true
3. 如果两个对象有相同的 hashcode 值, 它们也不一定是相等的
4. equals () 方法被覆盖时, hashcode () 方法也必须被覆盖
5. hashCode () 的默认行为是对堆上的对象产生独特值. 如果没有重写 hashCode (), 则该 class 的两个对象无论如何都不会相等, 即使这两个对象指向相同的数据

== 与 equals () 的区别

• 对于基本数据类型, == 比较的是 值是否相等
• 对于引用数据类型, == 比较的是 两个引用是否指向同一对象地址 (两者在内存中存放的地址 (堆内存地址) 是否指向同一个地方)
• 对于引用数据类型 (包括包装类型), 如果 equals () 方法没有被覆盖, 对比的就是它们的地址是否相等; 如果 equals () 方法被重写, 则比较的是地址内的内容

HashMap 的底层实现

JDK 1.8 之前

底层数据结构

JDK 1.8 之前 HashMap 底层是 数据 + 链表 结合在一起, 也就是 链表散列.

数组是 HashMap 的主体, 而链表主要是为了解决哈希冲突而存在的 (拉链法)

示图

元素存放位置的判断

HashMap 通过 key 的 hashcode 经过扰动函数处理后得到 hash 值

然后 HashMap 通过公式 (n - 1) & hash 判断当前元素的存放位置 (n : 数组的长度, hash : 当前元素的哈希值)

• 如果计算出的位置不存在元素的话, 则直接存入到计算位置
• 如果计算出的位置存在元素的话, 就判断该元素与要存入的元素的 hash 值是否相等
  • 如果不相同, 则通过 拉链法 解决冲突 (头插法插入链表, 即最新插入的元素在链头)
  • 如果相同, 则调用 equal () 方法判断两个 key 是否真的相同
    • 如果不同, 则通过 拉链法 解决冲突
    • 如果相同, 直接 覆盖

扰动函数

扰动函数就是 HashMap 的 hash () 方法

使用 hash () 主要是为了防止一些实现比较差的 hashCode () 方法 (使用扰动函数后可以减少碰撞)

JDK 1.8 之前的扰动函数扰动了 4 次, 比起 JDK 1.8 的扰动函数, 性能会差一些

源码

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

拉链法

拉链法 : 将链表和数组相结合

也就是说创建一个链表数组, 数组中每一格就是一个链表. 若遇到哈希冲突, 则将冲突的值加到链表中即可

示图

JDK 1.8

底层数据结构

JDK 1.8 中 HashMap 底层是 数据 + 链表 / 红黑树 结合在一起

当链表长度大于阙值 (默认为 8), 且数组长度大于等于 64 时, 会将链表转为红黑树, 减少搜索时间

当链表长度大于阙值 (默认为 8), 但数组长度小于 64 时, 则不会将链表转为红黑树, 而是进行数组扩容

示图

小贴士

TreeMap, TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树

红黑树就是为了解决二叉查找树的缺陷, 因为二叉查找树在某些情况下会退化成一个线性结构

扰动函数

JDK 1.8 更新了扰动函数, 相较于 JDK 1.8 之前的扰动函数, 性能更好

主体思路 : hashcode 值无符号右移 16 位后再亦或 hashcode 值

源码

static final int hash(Object key) {
    int h;
    // key.hashCode()：返回散列值也就是hashcode
    // ^ ：按位异或
    // >>>:无符号右移，忽略符号位，空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效, 尽量较少碰撞, 也就是要尽量把数据分配均匀.

Hash 值的范围值 -2147483648 到 2147483647, 前后加起来大概 40 亿的映射空间, 只要哈希函数映射得比较均匀松散, 一般应用是很难出现碰撞的. 但问题是一个 40 亿长度的数组, 内存是放不下的. 所以这个散列值是不能直接拿来用的. 用之前还要先做对数组的长度取模运算, 得到的余数才能用来要存放的位置也就是对应的数组下标.

这个数组下标的计算方法是 (n - 1) & hash (n 代表数组长度) 这也就解释了 HashMap 的长度为什么是 2 的幂次方

算法设计

思路原因

取余 (%) 操作中如果除数是 2 的幂次则等价于其余数减一的与 (&) 操作

前提

hash % n == hash & (n - 1) 的前提是 n 是 2 的 n 次方. (n 为数组长度)

采用与操作的原因

并且采用二进制操作与 (&), 相对于取余 (%) 操作能提高运算效率

HashMap 多线程操作导致死循环问题

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表.

不过, JDK 1.8 后解决了这个问题, 但是还是不建议在多线程下使用 HashMap, 因为多线程下使用 HashMap 还是会存在其他问题比如 数据丢失.

并发环境下推荐使用 ConcurrentHashMap

详细案例

疫苗：JAVA HASHMAP的死循环 (opens new window)

HashMap 常见的几种遍历方式

原文

HashMap 的 7 种遍历方式与性能分析！ (opens new window)

遍历方式分类

HashMap 遍历从大的方向来说, 可以分为 4 类 :

• 迭代器 (Iterator) 方式遍历
• For Each 方式遍历
• Lambda 方式遍历 (JDK 1.8)
• Stream API 方式遍历 (JDK 1.8)

具体的遍历方式有七种 :

• 使用迭代器 (Iterator) EntrySet 的方式遍历
• 使用迭代器 (Iterator) KeySet 的方式遍历
• 使用 For Each EntrySet 的方式遍历
• 使用 For Each KeySet 的方式遍历
• 使用 Lambda 的方式遍历
• 使用 Stream API 单线程的方式进行遍历
• 使用 Stream API 多线程的方式进行遍历

具体遍历方式实现代码

迭代器 EntrySet

代码

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, String> entry = iterator.next();
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
    }
}

迭代器 KeySet

代码

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            Integer key = iterator.next();
            System.out.println(key);
            System.out.println(map.get(key));
        }
    }
}

ForEach EntrySet

代码

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
    }
}

ForEach KeySet

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        for (Integer key : map.keySet()) {
            System.out.println(key);
            System.out.println(map.get(key));
        }
    }
}

Lambda

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        map.forEach((key, value) -> {
            System.out.println(key);
            System.out.println(value);
        });
    }
}

Streams API 单线程

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        map.entrySet().stream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}

Streams API 多线程

public class HashMapTest {
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // 遍历
        map.entrySet().parallelStream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}

性能分析

结果

结论

• EntrySet 的性能比 KeySet 的性能高出一倍多
• 使用迭代器或是 for 循环遍历 EntrySet 时, 性能是相同的
• 使用迭代器或是 for 循环遍历 KeySet 时, 性能是相同的

EntrySet 的性能比 KeySet 的性能高的原因

EntrySet 之所以比 KeySet 的性能高是因为, KeySet 在循环时使用了 map.get(key), 而 map.get(key) 相当于又遍历了一遍 Map 集合去查询 key 所对应的值. 为什么要用 "又" 这个词? 那是因为 在使用迭代器或者 for 循环时, 其实已经遍历了一遍 Map 集合了, 因此再使用 map.get(key) 查询时, 相当于遍历了两遍

而 EntrySet 只遍历了一遍 Map 集合, 之后通过代码 Entry<Integer, String> entry = iterator.next() 把对象的 key 和 value 值都放入到了 Entry 对象中, 因此再获取 key 和 value 值时就无需再遍历 Map 集合, 只需要从 Entry 对象中取值就可以了

所以, EntrySet 的性能比 KeySet 的性能高出了一倍, 因为 KeySet 相当于循环了两遍 Map 集合, 而 EntrySet 只循环了一遍

安全性测试

结论

• 迭代器中循环删除数据安全
• For 循环中删除数据非安全
• Lambda 循环中删除数据非安全
• Stream 循环中删除数据非安全

小结

我们不能在遍历中使用集合 map.remove() 来删除数据, 这是非安全的操作方式, 但我们可以使用迭代器的 iterator.remove() 的方法来删除数据, 这是安全的删除集合的方式. 同样的我们也可以使用 Lambda 中的 removeIf () 来提前删除数据, 或者是使用 Stream 中的 filter () 过滤掉要删除的数据进行循环, 这样都是安全的, 当然我们也可以在 for 循环前删除数据在遍历也是线程安全的

Lambda 正确删除方式

// 根据 map 中的 key 去判断删除
map.keySet().removeIf(key -> key == 1);
map.forEach((key, value) -> {
    System.out.println("show:" + key);
});

Stream 正确删除方式

map.entrySet().stream().filter(m -> 1 != m.getKey()).forEach((entry) -> {
    if (entry.getKey() == 1) {
        System.out.println("del:" + entry.getKey());
    } else {
        System.out.println("show:" + entry.getKey());
    }
});

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同

• 底层数据结构 :
  • ConcurrentHashMap 底层在 JDK 1.7 采用 分段的数组 + 链表 实现, 在 JDK 1.8 采用 数组 + 链表 / 红黑树 实现
  • Hashtable 底层采用 数组 + 链表 实现. 数组是 Hashtable 的主体, 链表则是主要为了解决哈希冲突存在的
• 实现线程安全的方式 :
  • ConcurrentHashMap
    • JDK 1.7 的时候, ConcurrentHashMap (分段锁) 对整个桶数组进行了分割分段 (segment), 每一把锁只锁容器的其中一部分数据, 多线程访问容器内不同数据段的数据, 就不会存在锁竞争, 提高并发访问率
    • JDK 1.8 的时候, ConcurrentHashMap 摒弃了 Segment 概念, 而是直接用 Node 数组 + 链表 / 红黑树 的数据结构来实现, 并发控制使用 synchronize 和 CAS 操作. 整个看起来就像优化过且线程安全的 HashMap
  • Hashtable (同一把锁) : 使用 synchronize 来保证线程安全, 因为只有一把锁, 同一时刻只能有一个线程工作, 所以效率非常低下.

Hashtable 原理图

JDK 1.7 的 ConcurrentHashMap

JDK 1.8 的 ConcurrentHashMap

JDK1.8 的 ConcurrentHashMap 不再是 Segment 数组 + HashEntry 数组 + 链表, 而是 Node 数组 + 链表 / 红黑树

不过, Node 只能用于链表的情况, 红黑树的情况需要使用 TreeNode. 当冲突链表达到一定长度时, 链表会转换成红黑树

Collections 工具类

Collections 工具类常用方法 :

• 排序
• 查找, 替换操作
• 同步控制 (不推荐)

Collections 内部结构

排序操作

// 反转
void reverse(List list)
// 随机排序
void shuffle(List list)
// 按自然排序的升序排序
void sort(List list)
// 定制排序, 由 Comparator 控制排序逻辑
void sort(List list, Comparator c)
// 交换两个索引位置的元素
void swap(List list, int i , int j)
// 旋转. 
// 当 distance 为正数时, 将 list 后 distance 个元素整体移到前面
// 当 distance 为负数时, 将 list 的前 distance 个元素整体移到后面
void rotate(List list, int distance)

查找, 替换操作

// 对 List 进行二分查找, 返回索引, 注意 List 必须是有序的
int binarySearch(List list, Object key)
// 根据元素的自然顺序, 返回最大的元素
int max(Collection coll)
// 根据元素的自然顺序, 返回最小的元素
int min(Collection coll)
// 根据定制排序, 返回最大元素, 排序规则由 Comparatator 类控制
int max(Collection coll, Comparator c)
// 根据定制排序, 返回最大元素, 排序规则由 Comparatator 类控制
int min(Collection coll, Comparator c)
// 用指定的元素代替指定 list 中的所有元素
void fill(List list, Object obj)
// 统计元素出现次数
int frequency(Collection c, Object o)
// 统计 target 在 list 中第一次出现的索引, 找不到则返回 -1
int indexOfSubList(List list, List target)
// 统计 target 在 list 中最后一次出现的索引, 找不到则返回 -1
int lastIndexOfSubList(List source, list target)
// 用新元素替换旧元素
boolean replaceAll(List list, Object oldVal, Object newVal)

同步控制

Collections 提供了多个 synchronizedXxx() 方法·, 该方法可以将指定集合包装成线程同步的集合, 从而解决多线程并发访问集合时的线程安全问题

我们知道 HashSet, TreeSet, ArrayList, LinkedList, HashMap, TreeMap 都是线程不安全的. Collections 提供了多个静态方法可以把他们包装成线程同步的集合

最好不要用下面这些方法, 效率非常低, 需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合

方法如下：

// 返回指定 collection 支持的同步（线程安全的）collection
synchronizedCollection(Collection<T>  c) 
// 返回指定列表支持的同步（线程安全的）List
synchronizedList(List<T> list)
// 返回由指定映射支持的同步（线程安全的）Map
synchronizedMap(Map<K,V> m) 
// 返回指定 set 支持的同步（线程安全的）set
synchronizedSet(Set<T> s)