集合详解

一、Collections 工具类和 Arrays 工具类常见方法

1、Collections 工具类常用方法:

以下都是静态方法：

1)排序

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

示例

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 rotate(List list, int distance)，旋转
Collections.rotate(arrayList, 4);
System.out.println("Collections.rotate(arrayList, 4):");
System.out.println(arrayList);

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

// void shuffle(List list),随机排序
Collections.shuffle(arrayList);
System.out.println("Collections.shuffle(arrayList):");
System.out.println(arrayList);

// void swap(List list, int i , int j),交换两个索引位置的元素
Collections.swap(arrayList, 2, 5);
System.out.println("Collections.swap(arrayList, 2, 5):");
System.out.println(arrayList);

//定制排序的用法
//降序
Collections.sort(arrayList, (o1, o2) -> o2.compareTo(o1));
System.out.println("定制排序后：");
System.out.println(arrayList);

2)查找替换操作

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

示例

		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);
		ArrayList<Integer> arrayList2 = new ArrayList<Integer>();
		arrayList2.add(-3);
		arrayList2.add(-5);
		arrayList2.add(7);
		System.out.println("原始数组:");
		System.out.println(arrayList);

		System.out.println("Collections.max(arrayList):");
		System.out.println(Collections.max(arrayList));

		System.out.println("Collections.min(arrayList):");
		System.out.println(Collections.min(arrayList));

		System.out.println("Collections.replaceAll(arrayList, 3, -3):");
		Collections.replaceAll(arrayList, 3, -3);
		System.out.println(arrayList);

		System.out.println("Collections.frequency(arrayList, -3):");
		System.out.println(Collections.frequency(arrayList, -3));

		System.out.println("Collections.indexOfSubList(arrayList, arrayList2):");
		System.out.println(Collections.indexOfSubList(arrayList, arrayList2));

		System.out.println("Collections.binarySearch(arrayList, 7):");
		// 对List进行二分查找，返回索引，List必须是有序的
		Collections.sort(arrayList);
		System.out.println(Collections.binarySearch(arrayList, 7));

3)同步控制(不推荐使用，建议使用JUC下的并发包)

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

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

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

方法如下：

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

4)不可变集合(只读)

emptyXxx() //返回一个空的、不可变的集合对象，此处的集合既可以是List，也可以是Set，还可以是Map。
singletonXxx() //返回一个只包含指定对象（只有一个或一个元素）的不可变的集合对象，此处的集合可以是：List，Set，Map。
unmodifiableXxx()//返回指定集合对象的不可变视图，此处的集合可以是：List，Set，Map。

• 上面三类方法的参数是原有的集合对象，返回值是该集合的**”只读“**版本。

实例

        //创建一个不可变的(不可添加)，空的List集合
        List<Object> objects = Collections.emptyList();
        //报错 java.lang.UnsupportedOperationException
        objects.add("hello");

2、Arrays类的场景操作

1)排序: sort()

• 只能是升序

        // *************排序 sort****************
        int[] a = { 1, 3, 2, 7, 6, 5, 4, 9 };
        // sort(int[] a)方法按照数字顺序排列指定的数组。
        //默认从小到大排序
        Arrays.sort(a);
        System.out.println("Arrays.sort(a):"+Arrays.toString(a));

        // sort(int[] a,int fromIndex,int toIndex)按升序排列数组的指定范围
        int b[] = { 1, 3, 2, 7, 6, 5, 4, 9 };
        Arrays.sort(b, 5, b.length-1);
        System.out.println("Arrays.sort(b, 2, 6):");
        for (int i : b) {
            System.out.print(i);
        }
        // 换行
        System.out.println();

2)查找 : binarySearch()

• 二分查找(前提是该数组有序，从小到大)

		// *************查找 binarySearch()****************
		char[] e = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
		// 排序后再进行二分查找，否则找不到
		Arrays.sort(e);
		System.out.println("Arrays.sort(e)" + Arrays.toString(e));
		System.out.println("Arrays.binarySearch(e, 'c')：");
		int s = Arrays.binarySearch(e, 'c');
		System.out.println("字符c在数组的位置：" + s);

3)比较: equals()

        // *************比较 equals****************
        char[] e = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
        char[] f = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
        /*
         * 元素数量相同，并且相同位置的元素相同。 另外，如果两个数组引用都是null，则它们被认为是相等的 。
         */
        // 输出true
        System.out.println("Arrays.equals(e, f):" + Arrays.equals(e, f));

4) 替换并填充 : fill()

		// *************填充fill(批量初始化)****************
		int[] g = { 1, 2, 3, 3, 3, 3, 6, 6, 6 };
		// 数组中所有元素重新分配值
		Arrays.fill(g, 3);
		System.out.println("Arrays.fill(g, 3)：");
		// 输出结果：333333333
		for (int i : g) {
			System.out.print(i);
		}
		// 换行
		System.out.println();

		int[] h = { 1, 2, 3, 3, 3, 3, 6, 6, 6, };
		// 数组中指定范围元素重新分配值 填充0,1的位置的元素，不包括2位置
		Arrays.fill(h, 0, 2, 9);
		System.out.println("Arrays.fill(h, 0, 2, 9);：");
		// 输出结果：993333666
		for (int i : h) {
			System.out.print(i);
		}

5)数组转集合 asList()

        // *************转列表 asList()****************
        /*
         * 返回由指定数组支持的固定大小的列表。
         * （将返回的列表更改为“写入数组”。）该方法作为基于数组和基于集合的API之间的桥梁，与Collection.toArray()相结合 。
         * 返回的列表是可序列化的，并实现RandomAccess 。
         * 此方法还提供了一种方便的方式来创建一个初始化为包含几个元素的固定大小的列表如下：
         */
        List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
        System.out.println(stooges);

注意：

• Arrays.asList()将数组转换为集合后,底层其实还是数组，使用集合的修改方法:add()、remove()、clear()会抛出异常。
• Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类,这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。
• Arrays.asList()是泛型方法，传入的对象必须是对象数组。(不能是基本类型，但是包装类型可以)

6) 数组转字符串 toString()

	// *************转字符串 toString()****************
		/*
		* 返回指定数组的内容的字符串表示形式。
		*/
		char[] k = { 'a', 'f', 'b', 'c', 'e', 'A', 'C', 'B' };
		System.out.println(Arrays.toString(k));// [a, f, b, c, e, A, C, B]

7)复制 copyOf()

		// *************复制 copy****************
		// copyOf 方法实现数组复制,h为数组，6为复制的长度
		int[] h = { 1, 2, 3, 3, 3, 3, 6, 6, 6, };
		int i[] = Arrays.copyOf(h, 6);
		System.out.println("Arrays.copyOf(h, 6);：");
		// 输出结果：123333
		for (int j : i) {
			System.out.print(j);
		}
		// 换行
		System.out.println();
		// copyOfRange将指定数组的指定范围复制到新数组中
		int j[] = Arrays.copyOfRange(h, 6, 11);
		System.out.println("Arrays.copyOfRange(h, 6, 11)：");
		// 输出结果66600(h数组只有9个元素这里是从索引6到索引11复制所以不足的就为0)
		for (int j2 : j) {
			System.out.print(j2);
		}
		// 换行
		System.out.println();

二、Collection集合详解

1、List集合

1)ArrayList

• 没有元素时大小为0，加入第一个元素时，初始化为10，扩容大小为原来的1.5倍

• 底层采用Object[] obj数组，增加元素采用数组拷贝的方式

• 查询快(根据索引直接定位)，增删慢(产生数组数据的移动)

• 线程不安全

2)Vector

• 底层采用Object[] obj数组，增加元素采用数组拷贝的方式。特点和ArrayList类似
• 线程安全(方法上加有synchronized)

3)LinkedList

• 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)
• 链表结构适增删快(无需移动数组，改变链表指针的指向即可)，查询慢(每次从头指针开始查询)

4)双向链表和双向循环链表

• 双向链表： 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
  • 
• **双向循环链表：**最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
  • 

5)RandomAccess接口

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以，在我看来 RandomAccess 接口不过是一个标识罢了。标识什么？ 标识实现这个接口的类具有随机访问功能。

6)常问

①ArrayList和Vector的区别？

• ArrayList是List主要的类，底层实现采用Object[]数组，适用于频繁查找工作，但是线程不安全
• Vector是List很早的类，底层也是采用Object[]数组，是线程安全的，故效率较低。

②ArrayList和LinkedList区别？

• 是否保证线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

• 底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。

• 是否支持快速随机访问：LinkedList不支持快速的随机元素访问，而ArrayList可以。快速的随机元素访问就是通过索引get(int index)快速定位元素的指定位置

• 内存空间占比：ArrayList的空间浪费主要是要在list列表的结尾会预留一定的空间容量，而LinkedList空间的花费主要是每个元素的都需要消耗比ArrayList更多的空间(因为要链表要存放直接后驱和直接前驱以及数据)

• 从增加和删除元素的位置移动：

  • ①ArrayList采用数组的存储方式，删除和插入元素需要移动元素，例如：默认添加元素在列表的末尾添加。如果要在指定索引位置i删除和插入元素的话，第i个和i之后的元素都要向后/前移动一位的操作
  • ②LinkedList采用链表的存储方式，默认对于插入和删除都无需移动元素。

③ArrayList扩容机制

• 以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10 ，ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右

2、Set集合

1)HashSet

• 不能存重复元素(存储重复的存储失败)，允许存储null元素。

• 储存和遍历的顺便可能不一致。使用迭代器变量元素

• （无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素

2)LinkedHashSet

• LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
• 存储和遍历的顺序是一致的。
• 可存储null元素

3)TreeSet

• 不能存重复元素(存储重复的存储失败)。不允许存储null元素，

• （有序，唯一）： 会将我们插入的元素重新排序。底层是红黑树(自平衡的排序二叉树)

4)常考

①Comparable和Comparator排序？

②equals 和 hashcode

相关规定

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

③ == 和 equals

对于基本类型来说，== 比较的是值是否相等；

对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址（两者在内存中存放的地址（堆内存地址）是否指向同一个地方）；

对于引用类型（包括包装类型）来说，equals 如果没有被重写，对比它们的地址是否相等；如果 equals()方法被重写（例如 String），则比较的是地址里的内容。

④HashSet如何去重

当传入对象到HashSet中时，根据对象的hashcode值(对象必须重写hashcode和equals方法，否则去重不成功)来判断对象加入的位置，若其他对象的hashcode的值与集合中已存在的对象的hashcode值比较，若相等的，则再调用equals来检查对象是否真的相等，若相等则认为是重复则插入失败。若hashcode相等，则直接认为重复的插入失败，这样判断对象是否重复的方法效率较高，先比较hashcode再比较equals中的对象值

3、Map集合

注意：若健值为自定义类型，必须重新hashcode和equals方法，否则不能保证唯一性

1)HashMap

• 默认大小为16，加载因子为0.75，即当元素数量为16*0.75=12时就会扩容。每次扩容为原数组长度的2倍。若指定了长度，则大于等于指定长度的2的幂次的第一个数。
• 非线程安全的
• 无序集合，存储和取出元素的顺序可能不一致
• 键值可为null
• JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间

2)LinkedHashMap

• 有序的集合，存储和取出的元素顺序一致

• LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

3)HashTable

• 健值都不能为null

• 线程安全的，所有方法加了synchronized，所有效率就低

• 哈希表(数组+链表)组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的

4)TreeMap

• 键不能null,值可以为null

• 会将我们插入的元素按照键值重新排序

• 红黑树（自平衡的排序二叉树）

5)常问

①HashMap和HashTable的区别

• 线程是否安全：HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）
• 效率：因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
• 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
• 初始容量大小和每次扩充容量大小的不同 ：
  • ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
  • ② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小
• 底层数据结构：JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

②HashMap和HashSet的区别

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap	HashSet
存储键值对	仅存储对象
实现了Map接口	实现了Set接口
使用put()存储元素	使用add()存储元素
HashMap 使用键（Key）计算 Hashcode	HashSet 使用成员对象来计算 hashcode 值，对于两个对象来说 hashcode 可能相同，所以 equals()方法用来判断对象的相等性

③HashMap和TreeMap的区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口

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

实现SortMap接口让 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);
            }
        });
        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());
        });
    }
}

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

4、集合遍历方式

1)List集合遍历

        ArrayList<String> list=new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println("-------for-------");
        //for遍历
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        System.out.println("------foreach--------");
        //foreach遍历
        for (String i : list) {
            System.out.println(i);
        }

        System.out.println("-------迭代器(forEach相当于迭代器)-------------");
        //迭代器forEach 不要在迭代过程中修改元素，否则抛 ConcurrentModificationException 异常。
        list.forEach(System.out::println);

        System.out.println("--------------迭代器iterator--------------------");
        //迭代器iteator
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

2)Set遍历方式

        TreeSet<String> hashSet=new TreeSet<>();
        hashSet.add("a");
        hashSet.add("b");
        hashSet.add("c");
        hashSet.add("d");
        hashSet.add("e");
        System.out.println("--------foreach------");
        //foreach遍历
        for (String i : hashSet) {
            System.out.println(i);
        }

        System.out.println("--------迭代器iterator(forEach)------");
        //迭代器forEach遍历
        hashSet.forEach(System.out::println);

        System.out.println("--------迭代器iterator------");
        //迭代器iterator遍历
        Iterator<String> iterator = hashSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

3)Map遍历方式

        HashMap<String,Integer> map=new HashMap<>();
        map.put("a", 1);
        map.put("c", 3);
        map.put("b", 2);
        map.put("e", 5);
        map.put("d", 4);

        System.out.println("------迭代器EntrySet(拿到整个key-value的实例)---------");
        //迭代器EntrySet
        Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Integer> next = iterator.next();
            System.out.println("键为:"+next.getKey()+"值为:"+next.getValue());
        }

        System.out.println("------迭代器KeySet(只拿到整个key)---------");
        //迭代器KeySet
        Iterator<String> iterator1 = map.keySet().iterator();
        while (iterator1.hasNext()) {
            //得到key
            String key = iterator1.next();
            System.out.println("键为:"+key+"值为:"+map.get(key));
        }

        System.out.println("------forEach(Lambda)---------");
        //forEach(Lambda表达式)
        map.forEach((key,value)->{
            System.out.println("键为:"+key+"值为:"+value);
        });

        System.out.println("------Stream API单线程---------");
        //StreamApi单线程
        map.entrySet().stream().forEach((entry)->{
            System.out.println("键:"+entry.getKey()+"值:"+entry.getValue());
        });

        System.out.println("------Stream API多线程---------");
        //StreamApi多线程
        map.entrySet().parallelStream().forEach((entry)->{
            System.out.println("键:"+entry.getKey()+"值:"+entry.getValue());
        });

4)安全和非安全的删除方式

• 非安全的删除方式：

  • foreach、Lambda的forEach、iteartor 中的方式：集合对象.remove(int index)
  • Stream中的：stream().forEach

• 安全的删除方式

  • for循环中的:集合对象.remove(int index)

  • iterator中: 迭代器对象.reomve()，删除当前正在遍历的元素

  • Lambda中删除的正确方式：(可以先使用 Lambda 的 removeIf 删除多余的数据，再进行循环)

    • List中：删除所有值为 a 的数据

      • //删除
        list.removeIf((i)->i=="a");
        //遍历
        list.forEach(item->{
           System.out.println(item);
        });
        

    • **Set中：**删除值为 a 的数据

      • hashSet.removeIf((i)->i=="a");
        hashSet.forEach(item->{
           System.out.println(item);
        });
        

    • **map中：**根据 map 中的 key 去判断删除，删除key为 a 的数据

      • map.keySet().removeIf((key)->key.equals("a"));
        map.forEach((key,value)->{
            System.out.println("键为:"+key+"值为:"+value);
        });
        

  • Stream中的: 针对map集合的，先用filter过滤掉我们不需要的值，再遍历。这里我们过滤key为 b 的值

    • map.entrySet().stream().filter(item-> "b"!=item.getKey()).forEach(entry->{
           System.out.println("键:"+entry.getKey()+"值:"+entry.getValue());
      });
      

三、HashMap详解

1.HashMap与HashTable区别

HashMap线程不安全，所以效率比较高

HashTable线程安全，效率低

HashMap的键和值可以都为null,为空的存放在数组的第0个位置

HashTable的键和值都不能为null ，其中一个为null都报错

2.实现HashMap的put和get操作

2.1 JDK1.7 HashMap的实现

数组+单向链表(头插法) 采用HashEntry封装键值对

public class MyArrayListMap<K,V> {

    /**
     * 存放HashEntry对象
     * 这里我们默认给1000，hashmap默认为16，加载因子为0.75
     */
    private HashEntry<K,V>[] hashEntries=new HashEntry[1000];

    class HashEntry<k,V>{
        k K;
        V v;
        public HashEntry(k k, V v) {
            this.K = k;
            this.v = v;
        }
    }
    /**
     * put操作
     * @param k
     * @param v
     */
    public void put(K k,V v){
//        根据我们的key计算hashcode，得出该key存放的index下标位置
//        对数组的长度取余操作得到下标
        int index = k.hashCode() % hashEntries.length;
        HashEntry hashEntry=new HashEntry(k, v);
        hashEntries[index]=hashEntry;
    }java

    public V get(K k){
//        时间复杂度为o(1)
         int index = k.hashCode() % hashEntries.length;
         return hashEntries[index].v;
    }

}

    public static void main(String[] args) {
        MyArrayListMap<Object,Object> myArrayListMap=new MyArrayListMap<>();
        myArrayListMap.put("a", "aaaa");
        myArrayListMap.put(97, "bbbb");
        Object lc = myArrayListMap.get("a");
        //bbbb
        System.out.println(lc);
    }

我们发现上述方法，上述代码可能存在hash碰撞的问题。当我们的存储的key算得的hashcode一致的时候，但是其值不一定相等。这就会导致后面的存的key会覆盖前面存的值情况。

1⃣️解决hashcode碰撞问题：

public class MyArrayListMap<K,V> {

    /**
     * 存放HashEntry对象
     * 这里我们默认给1000，hashmap默认为16，加载因子为0.75
     */
    private HashEntry<K,V>[] hashEntries=new HashEntry[1000];

    class HashEntry<k,V>{
        k K;
        V v;
        HashEntry next;

        public HashEntry(k k, V v) {
            this.K = k;
            this.v = v;
        }
    }
    /**
     * put操作
     * @param k
     * @param v
     */
    public void put(K k,V v){
//        根据我们的key计算hashcode，得出该key存放的index下标位置
//        对数组的长度取余操作得到下标
        int index = k.hashCode() % hashEntries.length;
//        该key对应的hashcode所在的对象
        HashEntry hashEntry = hashEntries[index];
//        要插入的对象
        HashEntry newHashEntry=new HashEntry(k, v);
//        判断该key所对应的hashcode在数组的位置是否存在
        if(hashEntry==null){
//            不存在，直接插入此位置
            hashEntries[index] = newHashEntry;
            return;
        }
//        此位置若有此值(hashcode相同)
//        直接插入到该链表的下一个位置
//        jdk1.8 hashmap使用的尾插法
        hashEntry.next=newHashEntry;

//        jdk1.7 hashmap采用的链表头插法  头插发极易在多线程扩容的情况下造成死链。
//        newHashEntry.next=hashEntry;
//        hashEntries[index]=newHashEntry;

    }

    public V get(K k){
//        时间复杂度为o(1)
         int index = k.hashCode() % hashEntries.length;
//        遍历该位置上的链表
        for (HashEntry hashEntry = hashEntries[index]; hashEntry != null; hashEntry=hashEntry.next) {
//            如果key值相等; 或者基本数据类型相等
            if(hashEntry.K.equals(k)||hashEntry.K==k){
//                直接返回值
                return (V) hashEntry.v;
            }
        }
        return null;
    }
}

    public static void main(String[] args) {
        MyArrayListMap<Object,Object> myArrayListMap=new MyArrayListMap<>();
        myArrayListMap.put("a", "aaaa");
        myArrayListMap.put(97, "bbbb");
        Object lc = myArrayListMap.get("a");
        //aaaa
        System.out.println(lc);
    }

我们可以在hashcode碰撞的位置加入链表进行存储。jdk1.8 hashmap使用的尾插法(多线程环境下出现扩容丢失)。jdk1.7 hashmap采用的链表头插法(在扩容的时候容易发生死链)

2⃣️死链问题：

HashMap之所以在并发下的扩容造成死循环，是因为，多个线程并发进行时，因为一个线程先期完成了扩容，将原的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。于是形成了一个环形链表，当表中不存在的元素时，造成死循环。

虽然在JDK1.8中，Java的开发小组修正了这个问题，但是HashMap始终存在着其他的线程安全问题。所以在并发情况下，我们应该使用HastTable或者ConcurrentHashMap来代替HashMap。

时间复杂度：

• 在hashcode没有产生冲突的情况下时间复杂度为O(1),此时可以直接通过hashcode值直接得到此值。

• 在hashcode产生冲突时,时间复杂度为O(n),此时需要遍历该处的链表。

2.1 JDK1.8 HashMap的实现

数组+链表(尾插法)+红黑树

数组时间复杂度o(1);

链表时间复杂度o(n);

红黑数时间复杂度o(logn)

在jdk1.8，当链表的长度大于8的情况下并且数组的长度是64的情况下转换为红黑树(平衡二叉树，左旋和右旋)存放

3. HashMap扩容机制

HashMap数组默认的容量为16，加载因子为0.75

16*0.75=12. 当存放的数据为12时，即对原来的数组进行扩容为2倍。即32

如果加载因子太小的情况下，key冲突的概率比较小的，即存放一点数据就扩容，但是这样非常浪费空间

如果加载因子太大的情况下，key冲突的概率比较大的，即数组快满的时候才扩容，这样利用的空间非常好。

通过大量测试，发现取平衡值0.75最优。

​