1.12Java-集合

古城微笑少年丶 2024-04-01 08:49 51阅读 0赞

**目录**

1.12.1集合

1.12.1.1什么是集合

1.12.1.2集合体系

1.12.2Collection接口

1.12.2.1 Collection概述

1.12.2.2 Collection方法

1.12.2.3List集合

1.12.2.3.1List集合概述

1.12.2.3.2List集合特点

1.12.2.3.3List集合常用方法

1.12.2.3.4ArrayList集合

1.12.2.3.5LinkedList集合

1.12.2.4Set接口

1.12.2.4.1Set接口概述

1.12.2.4.2HashSet集合

HashSet集合存储数据的结构

1.12.2.4.3TreeSet集合

1.12.2.4.4LinkedHashSet集合

\*1.12.3Map集合

1.12.3.1Map接口中常用的方法

1.12.3.1.1

1.12.3.1.2 Map集合的遍历

\*1.12.3.2HashMap

1.12.3.2.1 为什么使用HashMap

1.12.3.2.2 HashMap是如何get()和put()

1.12.3.2.3 HashMap扩容-resize

1.12.3.2.4 扩容死循环问题

1.12.3.2.5 JDK8引入红黑树

1.12.3.2.6 数据覆盖

1.12.3.2.7 HashMap 线程安全吗？

1.12.3.2.8 HashMap在java1.8和java1.7的区别

1.12.3.3 HashTable

1.12.3.4 ConcurrentHashMap

1.12.3.5 LinkedHashMap

--------------------

！！看此章节前一定要先看该系列的 1.11数据结构，因为此章节涉及链表、HashMap等数据结构方面的知识点。

## 1.12.1集合 ##

### 1.12.1.1什么是集合 ###

在java中我们可以使用数组来保存多个对象，但是数组的长度不可变。如果需要保存数量变化的数据，数据就不太合适了。为了保存数量不确定的数据，以及保存具有映射关系的数据（也被称为关联数组），Java 提供了集合类。集合类主要负责保存、盛装其他数据，因此集合类也被称为容器类

**集合**：集合是java中提供的一种容器，可以用来存储多个数据,并且可以存储任意类型的数据

### 1.12.1.2集合体系 ###

集合按照其存储结构可以分为两大类：

> 单列集合`java.util.Collection`
> 
> 双列集合`java.util.Map`

何为单列双列？

简单来说，单列就是只有一个值，双列是（key（建） = value（值)）键值对。

举例：

定义一个String \[ \] a，a数组里面存的 a\[ \]=\{"张三","李四"\}，a\[0\]的值就是张三，这就是单列集合

定义一个map map则是根据key来提取value 。map\{name1="张三"，name2=“李四”\}，name对应的vlaue就是张三。

这里涉及到数据结构，详细的数据结构会在下面的章节详细讲解。

![1e7353eb6bbd43d584e829a54f3eecc9.png][]

### 1.12.2Collection接口 ###

### 1.12.2.1 Collection概述 ###

Collection是所有单列集合的父接口，Collection中定义了单列集合(List、Set)通用的一些方法，这些方法可用于操作所有的单列集合。

### 1.12.2.2 Collection方法 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td>public boolean add(E e)</td> 
   <td>把给定的对象添加到当前集合中 。</td> 
  </tr> 
  <tr> 
   <td>public boolean remove(E e)</td> 
   <td>把给定的对象在当前集合中删除。</td> 
  </tr> 
  <tr> 
   <td>public boolean contains(E e)</td> 
   <td>判断当前集合中是否包含给定的对象。</td> 
  </tr> 
  <tr> 
   <td>public boolean isEmpty()</td> 
   <td>判断当前集合是否为空。</td> 
  </tr> 
  <tr> 
   <td>public int size()</td> 
   <td>返回集合中元素的个数。</td> 
  </tr> 
  <tr> 
   <td>public Object[] toArray()</td> 
   <td>把集合中的元素，存储到数组中。</td> 
  </tr> 
  <tr> 
   <td>public void clear()</td> 
   <td>清空集合中所有的元素。</td> 
  </tr> 
 </tbody> 
</table>

### 1.12.2.3List集合 ###

![31b16660f7104713b458e6457f7042a5.png][]

#### 1.12.2.3.1**List集合概述** ####

`java.util.List`接口继承自`Collection`接口，将实现了`List`接口的对象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过索引来访问集合中的指定元素。另外，List集合还有一个特点就是元素有序，即元素的存入顺序和取出顺序一致。

#### 1.12.2.3.2**List集合特点** ####

*  它是一个元素存取有序的集合。例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。
 *  它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。
 *  集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

#### 1.12.2.3.3**List集合常用方法** ####

<table style="width:582px;"> 
 <tbody> 
  <tr> 
   <th style="width:232px;">方法名</th> 
   <th style="width:349px;">说明</th> 
  </tr> 
  <tr> 
   <td style="width:232px;">public void add(int index, E element)</td> 
   <td style="width:349px;">将指定的元素，添加到该集合中的指定位置上。</td> 
  </tr> 
  <tr> 
   <td style="width:232px;">public E get(int index)</td> 
   <td style="width:349px;">返回集合中指定位置的元素·。</td> 
  </tr> 
  <tr> 
   <td style="width:232px;">public E remove(int index)</td> 
   <td style="width:349px;">移除列表中指定位置的元素, 返回的是被移除的元素。</td> 
  </tr> 
  <tr> 
   <td style="width:232px;">public E set(int index, E element)</td> 
   <td style="width:349px;">用指定元素替换集合中指定位置的元素,返回值的更新前的元素。</td> 
  </tr> 
 </tbody> 
</table>

#### 1.12.2.3.4 ArrayList集合 ####

![31b16660f7104713b458e6457f7042a5.png][]

`java.util.ArrayList`集合数据存储的结构是数组结构。

元素增删慢，查找快，由于日常开发中使用最多的功能为查询数据、遍历数据，所以`ArrayList`是最常用的集合。

思考ArrayList为什么有这样的特性？

ArrayList底层是数组，数组是按顺序存储的，如果增删，整个数组的大部分位置都要跟着移动，比如删除数组中间一个元素，那被删除元素后面的所有元素都要前移。

为什么查询遍历快呢？，因为只要按着下标顺序依次走下去就可以，不需要再额外什么索引、指针之类的乱七八糟的东西。

**ArrayList常用方法**

<table style="width:571px;"> 
 <tbody> 
  <tr> 
   <th style="width:228px;">方法名</th> 
   <th style="width:342px;">说明</th> 
  </tr> 
  <tr> 
   <td style="width:228px;">public void add(int index, E element)</td> 
   <td style="width:342px;">将指定的元素，添加到该集合中的指定位置上。</td> 
  </tr> 
  <tr> 
   <td style="width:228px;">public E get(int index)</td> 
   <td style="width:342px;">返回集合中指定位置的元素·。</td> 
  </tr> 
  <tr> 
   <td style="width:228px;">public E remove(int index)</td> 
   <td style="width:342px;">移除列表中指定位置的元素, 返回的是被移除的元素。</td> 
  </tr> 
  <tr> 
   <td style="width:228px;">public E set(int index, E element)</td> 
   <td style="width:342px;">用指定元素替换集合中指定位置的元素,返回值的更新前的元素。</td> 
  </tr> 
  <tr> 
   <td style="width:228px;">public boolean add(E e)</td> 
   <td style="width:342px;">将指定的元素添加到此列表的尾部</td> 
  </tr> 
 </tbody> 
</table>

#### 1.12.2.3.5 Vector集合 ####

vector底层也是数组

vector是线程安全，Vector类的操作方法带有synchronized；

已被舍弃使用

**Vector与ArrayList的区别**

1.  ArrayList在内存不够时默认扩展50%+1个，Vector默认扩展一倍
2.  Vector提供indexof(obj,start)，ArrayList没有
3.  Vector属于线程安全级别，但大对数情况下不使用，因为线程安全需要大的系统开销

#### 1.12.2.3.6 LinkedList集合 ####

![31b16660f7104713b458e6457f7042a5.png][]

`java.util.LinkedList`集合数据存储的结构是双向链表结构。方便元素添加、删除的集合。

实际开发中对一个集合元素的添加与删除经常涉及到首尾操作，而LinkedList提供了大量首尾操作的方法。这些方法我们作为了解即可：

**LinkedList常用方法**

<table style="width:582px;"> 
 <tbody> 
  <tr> 
   <th style="width:281px;">方法名</th> 
   <th style="width:300px;">说明</th> 
  </tr> 
  <tr> 
   <td style="width:281px;">public void addFirst(E e)</td> 
   <td style="width:300px;">将指定元素插入此列表的开头。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public void addLast(E e)</td> 
   <td style="width:300px;">将指定元素添加到此列表的结尾。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public E getFirst()</td> 
   <td style="width:300px;">返回此列表的第一个元素。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public E getLast()</td> 
   <td style="width:300px;">返回此列表的最后一个元素。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public E removeFirst()</td> 
   <td style="width:300px;">移除并返回此列表的第一个元素。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public E removeLast()</td> 
   <td style="width:300px;">移除并返回此列表的最后一个元素。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public E pop()</td> 
   <td style="width:300px;">从此列表所表示的堆栈处弹出一个元素。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public void push(E e)</td> 
   <td style="width:300px;">将元素推入此列表所表示的堆栈。</td> 
  </tr> 
  <tr> 
   <td style="width:281px;">public boolean isEmpty()</td> 
   <td style="width:300px;">如果列表不包含元素，则返回true。</td> 
  </tr> 
 </tbody> 
</table>

#### 1.12.2.3.7 阐述 ArrayList、Vector、LinkedList 的存储性能和特性 ####

ArrayList 和 Vector 都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢。

Vector 中的方法由于添加了 synchronized 修饰，因此 Vector 是线程安全的容器，但性能上较 ArrayList 差，因此已经是 Java 中的遗留容器。

LinkedList 使用双向链表实现存储（将内存中零散的内存单元通过附加的引用关联起来，形成一个可以按序号索 引的线性结构，这种链式存储方式与数组的连续存储方式相比，内存的利用率更 高），按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

但是由于 ArrayList 和 LinkedListed 都是非线程安全的，如果遇到多个线程操作同一个容器的场景，则可以通过工具类 Collections 中的 synchronizedList 方法将其转换成线程安全的容器后再使用（这 是对装潢模式的应用，将已有对象传入另一个类的构造器中创建新的对象来增强实现）。

### 1.12.2.4Set接口 ###

![31b16660f7104713b458e6457f7042a5.png][]

#### 1.12.2.4.1**Set接口概述** ####

`java.util.Set`接口和`java.util.List`接口一样，同样继承自`Collection`接口，它与`Collection`接口中的方法基本一致，并没有对`Collection`接口进行功能上的扩充，只是比`Collection`接口更加严格了。与`List`接口不同的是，`Set`接口中元素无序（存入和取出元素的顺序不一致），并且都会以某种规则保证存入的元素不出现重复。

**Set 特点**

*  Set集合中的元素不可重复、无序
 *  Set集合没有索引

`Set`集合有多个子类，这里我们介绍其中的`java.util.HashSet`、`java.util.LinkedHashSet`这两个集合。

#### 1.12.2.4.2HashSet集合 ####

![31b16660f7104713b458e6457f7042a5.png][]

**什么是HashSet**

`java.util.HashSet`是`Set`接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。`java.util.HashSet`底层的实现其实是一个`java.util.HashMap`支持。

![2db1391b6240402ab3d3eab5ac809736.png][]

`HashSet`是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于：`hashCode`与`equals`方法。

**HashSet的特点**

*  HashSet集合中的元素不可重复
 *  HashSet集合没有索引
 *  HashSet集合是无序的(存储元素的顺序与取出元素顺序可能不一致)
 *  也有HashMap的特性：
    
     *  可以存放null,只能存一个null

【**重点来了**】

上面的都是一些“肤浅”的概念，但是这些“肤浅”的概念，每一个都值得深度剖析，注意，深度剖析涉及到JVM底层架构，如果没有对于JVM不熟悉的，可以先跳过这里，等学完1.23JVM后再回过头来看这些知识点。

上面说到HashSet集合中的元素不可重复，那我们来写一段代码

//定义一个Student类 
    class Student {
        private String name;
    
        public Student(String name) {
            this.name = name;
        }
    }
    
    
    //main方法
    public class Test {
        public static void main(String[] args) {
            HashSet hashSet = new HashSet();
            hashSet.add("student");
            hashSet.add("student");
            System.out.println(hashSet);
            System.out.println(new Student("student"));
            System.out.println(new Student("student"));
    
        }
    }

里面分别添加两个字符串：student,和两个Student对象：student。试猜想结果如何？只有一个student字符串和一个student对象？

运行结果：

![2f04be9e267a4ea0af7f6598763273e3.png][]

为什么student对象有两个？？

我们先解读com.lb.basic.Student@1b6d3586

> com.lb.basic.Student：是包名.类名
> 
> @：就是个分隔符，@后面的一串数字你表示@前的“这玩意”在内存中的地址

我们发现，原来同样的new Student("student")，居然是不同的地址也就是说这两个对象完全不一样。

因为引用类型，详细已经在1.1中仔细讲解过【点击跳转1.1】

我们接着实验，加入以下代码

//新加入
            hashSet.add(new String("student1"));
            hashSet.add(new String("student1"));
            System.out.println(hashSet);

根据上面的例子，我们可能会想，String是个类，和上面一样，这俩肯定不一样，得出结论：hashset中有俩String对象。

运行结果：

![51d98457273843fd835038e11ab1f2f6.png][]

为啥？为什么只有一个student1？

哎更不对啊，为什么这个格式是 student1 ，而不是 包名.String@地址

待更新------------------------

#### HashSet集合存储数据的结构 ####

JDK的版本不同，HashSet集合的数据结构有所不同：

>  *  JDK8之前：数组+链表 (现在几乎不用)
>  *  JDK8之后：数组+链表+红黑树

以上数据结构我们称之为是哈希表

让我们把这简短的理论深度剖析下：

什么是数组+链表？

如图就是一个数组+链表组合

![e73c982778704c29ba02aea463d7b9fb.png][]

public class HashSetStructure {
        public static void main(String[] args) {
            //模拟HsahSet
            //1.创建一个数组，数组类型是Node[]
            Node[] table =new Node[16];
          // 创建结点
            Node a = new Node("a",null);
            table[2]=a;
            Node b = new Node("b",null);
            a.next=b;
            Node c = new Node("c",null);
           table[3]=c;
            System.out.println("table:"+table);
    
        }
    }
    class Node{ //结点  存储数据
        Object item; //存放数据
        Node next; //指向下一个结点
    
        public Node(Object item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

我们DEBUG查看

![0410f18239064d1b9b084238b79f985a.png][]

a=\[Node@490\]是结点a的地址，a是存储在数组下标为2中，a里面的next指向的就是b的地址，由于b没有next，所以b的next为null。c存储在数组下标为3。

为什么要把存储结构设计成这样?

HashSet元素添加底层的机制是什么样？

由于HashSet的底层是HashMap，所以底层肯定和HashMap有很大的关联。

添加元素时，根据HashCode得到索引，找到存储数据的表。查看索引位置是否有元素，没有元素，就添加；有元素，调用equals比较，相同就放弃添加，不相同，就添加已有结点后面，形成一个链表（拉链法），参考下图。

![e73c982778704c29ba02aea463d7b9fb.png][]

如果一条链表的元素个数到达 TREEIFY\_THRESHOLD（默认8），并且表的大小> MIN\_TREEIFY\_CAPACITY(默认64)，就会转为红黑树。

![f9eec283a143496484809e48e8fab127.png][]

待更新---------------------

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
    //定义一些辅助变量
            Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 这个if 表示：当前table 为null,就会对table表扩容，大小为16
    这个table是hashmap的属性，用来放Node结点的数组，数组+链表结构中，链表的头节点不就是存放在数组中，这个table就是这个数组
            if ((tab = table) == null || (n = tab.length) == 0)
    //如果table为空，会调用resize()方法，我们进入到resize()方法中，代码看resize()部分
    //返回table   大小为16
                n = (tab = resize()).length;
    //if语句中  根据当前key计算出的hash值去计算该key应该存放到table的哪个索引位置，并且把这个位置的对象赋给p   并判断p是否为null
    //如果p为null,说明当前位置没有元素，就创建Node（hash,key="真正的值",value="PRESENT"，null）,存入hash的作用是，用作以后判断，把创建好的结点放到数组tab[i]中
            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;
        }

resize()

final Node<K,V>[] resize() {
    
            Node<K,V>[] oldTab = table;
    //因为table为null,这里的三目运算  oldCap 为0
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                -----省略
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                ------省略
            else {               // zero initial threshold signifies using defaults
    /*程序执行这里  
    DEFAULT_INITIAL_CAPACITY：16
    DEFAULT_LOAD_FACTOR：0.75  负（加）载因子
    (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)：12  这里的设计是初始空间大小为16，当用到12时就会扩展空间，防止有大量数据存入，导致内存不够造成阻塞/内存不足
    
    
     */           newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
    //
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            -----省略
    //返回  大小为16
             return newTab;

韩顺平老师的

[23\_Java集合专题\_HashSet扩容机制\_哔哩哔哩\_bilibili][23_Java_HashSet_bilibili]

#### 1.12.2.4.3TreeSet集合 ####

#### 1.12.2.4.4LinkedHashSet集合 ####

我们知道HashSet保证元素唯一，可是元素存放进去是没有顺序的，那么我们要保证有序，怎么办呢？

在HashSet下面有一个子类`java.util.LinkedHashSet`，它是链表和哈希表组合的一个数据存储结构。

**LinkedHashSet集合特点**

*  LinkedHashSet集合中的元素不可重复
 *  LinkedHashSet集合没有索引
 *  LinkedHashSet集合是有序的(存储元素的顺序与取出元素顺序一致)

## **\***1.12.3Map集合 ##

![1e7353eb6bbd43d584e829a54f3eecc9.png][]

**映射：**

首先我们需要了解什么是映射。比如我们的身份证号，正常来说，每个人有唯一的身份证号，用来唯一标识，而这个身份证号和个人这种一一对应的关系称为映射。

Java提供了专门的集合类用来存放这种对象关系的对象，即`java.util.Map`接口。

我们通过查看`Map`接口描述，发现`Map`接口下的集合与`Collection`接口下的集合，它们存储数据的形式不同。

### 1.12.3.1Map接口中常用的方法 ###

#### 1.12.3.1.1 ####

<table style="width:670px;"> 
 <tbody> 
  <tr> 
   <th style="width:299px;">方法名</th> 
   <th style="width:369px;">说明</th> 
  </tr> 
  <tr> 
   <td style="width:299px;">public V put(K key, V value)</td> 
   <td style="width:369px;">把指定的键与指定的值添加到Map集合中。</td> 
  </tr> 
  <tr> 
   <td style="width:299px;">public V remove(Object key)</td> 
   <td style="width:369px;">把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的值。</td> 
  </tr> 
  <tr> 
   <td style="width:299px;">public V get(Object key)</td> 
   <td style="width:369px;">根据指定的键，在Map集合中获取对应的值。</td> 
  </tr> 
  <tr> 
   <td style="width:299px;">boolean containsKey(Object key)</td> 
   <td style="width:369px;">判断集合中是否包含指定的键。</td> 
  </tr> 
  <tr> 
   <td style="width:299px;">public Set&lt;K&gt; keySet()</td> 
   <td style="width:369px;">获取Map集合中所有的键，存储到Set集合中。</td> 
  </tr> 
  <tr> 
   <td style="width:299px;">public Set&lt;Map.Entry&lt;K,V&gt;&gt; entrySet()</td> 
   <td style="width:369px;">获取到Map集合中所有的键值对对象的集合(Set集合)。</td> 
  </tr> 
 </tbody> 
</table>

#### 1.12.3.1.2 Map集合的遍历 ####

**keySet**

即通过元素中的键，获取键所对应的值

> 1. 获取Map中所有的键，由于键是唯一的，所以返回一个Set集合存储所有的键。方法提示:keyset()  
> 2. 遍历键的Set集合，得到每一个键。  
> 3. 根据键，获取键所对应的值。方法提示:get(K key)

public class MapDemo01 {
        public static void main(String[] args) {
            //创建Map集合对象 
            HashMap<String, String> map = new HashMap<String,String>();
            //添加元素到集合 
            map.put("name", "张三");
            map.put("sex", "男");
            map.put("age", "20");
            //获取所有的键  获取键集
            Set<String> keys = map.keySet();
            // 遍历键集 得到 每一个键
            for (String key : keys) {
                //key 就是键
                //获取对应值
                String value = map.get(key);
                System.out.println(key+"："+value);
            }  
        }
    }

**Entry**

`Map`中存放的是两种对象，一种称为**key**(键)，一种称为**value**(值)，它们在在`Map`中是一一对应关系，这一对对象又称做`Map`中的一个`Entry(项)`。`Entry`将键值对的对应关系封装成了对象。即键值对对象，这样我们在遍历`Map`集合时，就可以从每一个键值对（`Entry`）对象中获取对应的键与对应的值。

**获取Entry**

public Set<Map.Entry<K,V>> **entrySet()**: 获取到Map集合中所有的键值对对象的集合(Set集合)。

**Entry对象常用方法**

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <th>方法名</th> 
   <th>说明</th> 
  </tr> 
  <tr> 
   <td>public K getKey()</td> 
   <td>获取Entry对象中的键。</td> 
  </tr> 
  <tr> 
   <td>public V getValue()</td> 
   <td>获取Entry对象中的值。</td> 
  </tr> 
 </tbody> 
</table>

> 1. 获取Map集合中，所有的键值对(Entry)对象，以Set集合形式返回。方法提示:entrySet()  
> 2. 遍历包含键值对(Entry)对象的Set集合，得到每一个键值对(Entry)对象。  
> 3. 通过键值对(Entry)对象，获取Entry对象中的键与值。 方法提示:getkey() getValue()

public class Map {
        public static void main(String[] args) {
            // 创建Map集合对象 
            HashMap<String, String> map = new HashMap<String,String>();
            // 添加元素到集合 
            map.put("name", "张三");
            map.put("sex", "男");
            map.put("age", "28");
            // 获取 所有的 entry对象  entrySet
            Set<Entry<String,String>> entrySet = map.entrySet();
            // 遍历得到每一个entry对象
            for (Entry<String, String> entry : entrySet) {
               	// 解析 
                String key = entry.getKey();
                String value = entry.getValue();  
                System.out.println(key+":"+value);
            }
        }
    }

### \*1.12.3.2HashMap ###

![1cd254ea9f444b98a87f736460654275.png][]

> 存储数据采用的哈希表结构，元素的存取顺序不能保证一致。由于要保证键的唯一、不重复，需要重写键的hashCode()方法、equals()方法。

关于HashMap我们不能只记得这些简单的理论，在面试中，经常涉及到很深入的问题，下面我们来深度剖析HashMap

#### 1.12.3.2.1 **为什么使用HashMap** ####

对于要求查询次数特别多，查询效率比较高同时插入和删除的次数比较少的情况下，通常会选择ArrayList，因为它的底层是通过数组实现的。对于插入和删除次数比较多同时在查询次数不多的情况下，通常会选择LinkedList，因为它的底层是通过链表实现的。

但现在同时要求插入，删除，查询效率都很高的情况下我们该如何选择容器呢？  
那么就有一种新的容器叫HashMap，他里面既有数组结构，也有链表结构，所以可以弥补相互的缺点。而且HashMap主要用法是get()和put() 。

#### 1.12.3.2.2 HashMap是如何get()和put() ####

![171ffde446b746aca5771750f3cdeebc.png][]

**put操作**

1.  判断数组是否为空，为空进行初始化;
2.  不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
3.  查看 table\[index\] 是否存在数据，没有数据就构造一个Node节点存放在 table\[index\] 中；
4.  存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
5.  如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)
6.  如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于8并且数组长度大于64，大于的话链表转换为红黑树；
7.  插入完成之后判断当前节点数是否大于阈值（capacity\*loadFactor），如果大于开始扩容为原数组的二倍。

**get操作**

1.  调用hash(key)方法获取key对应的hash值从而获取该键值对在数组中的下标。
2.  对链表进行顺序遍历，使用equals()方法查找链表中相等的key对应的value值。

**如何初始化的？**

使用new HashMap()，当不传值，默认大小是16，负载因子是0.75。如果传入参数K，那么初始化容量大小为大于K的2的最小整数幂。比如传入的是10，2的3次方等于8，2的4次方的16，16>10，

所以初始化容量大小就是16（2的4次方）。

**为什么HashMap的数组长度要取2的整数幂？**

1、运算效率

&运算是个很基本的运算符 只有1&1=1，其余均为0。我们刚好利用这个性质进行取模运算

传统取模运算： %模长，速度慢

&运算取值运算：&(模长-1)，速度快，前提：模长为二的幂次方

如模长cen=4，二进制为100，对模长-1，得到模长为011，正好最高位为0，其余为1，这也是正好利用了二的幂次方减一的这一特性，使得结果与传统取余操作等价(110&011=010)

2、散列性

作为散列表，冲突性是无法避免的，所以为了减少碰撞，我们需要将值尽可能的均匀散列

假设，key1=1010,

模长不设置二的幂次方，cen=1101，1010&1101=1000。这时有个key2=1000，1000&1101=1000,发生冲突。

若模长改为二的幂次方减一

key1=1010,cen=1101，1010&(1000-1)=1010&1111=1010。这时有个key2=1000,1000&(1000-1)=1000&1111=1000,不发生冲突。

#### 1.12.3.2.3 **HashMap扩容-resize** ####

当HashMap中的元素越来越多的时候，碰撞的几率也就越来越高，所以为了提高查询的效率，就要对HashMap的数组进行扩容。与此同时，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

追问：为什么要对原数组中元素再重新进行一次hash？直接复制到新数组不行吗？

因为数组长度扩大以后Hash规则也会随之变化。  
Hash的公式： index = HashCode（Key） & （Length - 1）

那么HashMap什么时候才扩容呢？

当HashMap中的元素个数超过 **initailCapacity** x **loadFactor** 时，就会进行数组扩容。

> 默认值：
> 
> initailCapacity ，初始容量：16
> 
> loadFactor，负载因子：0.75 （泊松分布计算出的）

所以，当HashMap中元素个数超过16\*0.75=12的时候，就把数组的大小扩展为2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作。

HashMap计算添加元素的位置时，使用的位运算，这是特别高效的运算；另外，HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞。

> 1.7是先判断是否需要扩容，再进行插入操作。1.8是先插入，插入完成之后再判断是否需要扩容

#### 1.12.3.2.4 **扩容死循环问题** ####

HashMap是一个线程不安全的容器，我们考虑最差的情况，所有元素都定位到同一个位置，形成一个很长的链表。当取值时最坏情况需要遍历所有节点，时间按复杂度变成了O(n)。  
JDK1.7中HashMap采用头插法拉链表，所谓头插法，即在每次都在链表头部插入最后添加的数据。

**由于HashMap是线程不安全的，在多线程时会出现死循环问题**

以下场景为多线程：  
假设在原来的链表中，A节点指向了B节点。  
在线程1进行扩容时，由于使用了头插法，链表中B节点指向了A节点。  
在线程2进行扩容时，由于使用了头插法，链表中A节点又指向了B节点。  
在线程n进行扩容时，**…**  
在并发扩容结束后，可能导致A节点指向了B节点，B节点指向了A节点，链表中便有了环！！！

导致的结果：CPU占用率100%

#### 1.12.3.2.5 **JDK8引入红黑树** ####

HashMap底层就变成了 **数组+链表+红黑树**

为了解决JDK1.7中的死循环问题， 在JDK1.8中新增加了红黑树，即在数组长度大于64，同时链表长度大于8的情况下，链表将转化为红黑树。同时使用尾插法。当数据的长度退化成6时，红黑树转化为链表。

> 这个选择是综合各种考虑之下的，既要put效率很高，同时也要get效率很高，红黑树就是其中一种。

讲红黑树之前，先来了解以下二叉排序树

1.  左子树上所有结点的值均小于或等于它的根结点的值。
2.  右子树上所有结点的值均大于或等于它的根结点的值。
3.  左、右子树也分别为二叉排序树。

![10da949ef2e042a387b132e5aaa49e5b.png][]

如果要查找10。先看根节点9，由于10 > 9，因此查看右孩子13；由于10 < 13，因此查看左孩子11；由于10 < 11，因此查看左孩子10，发现10正是要查找的节点；这种方式查找最大的次数等于二叉排序树的高度。 复杂度为O(log n)

同时二叉排序树也有一些问题

当只有三个节点

![ad7470e86de34edf84c360efd59d7f98.png][]

我们往树中插入7，6，5，4节点

![89ec1521f7164eb7896b76002d3a44fd.png][]

随着树的深度增加，那么查找的效率就变得非常差了，变成了O(n)，就不具有二叉排序树的优点了。

因此引入红黑树

红黑树是一种自平衡的二叉排序树

有以下特性：

1.  节点是红色或黑色；
2.  根节点是黑色；
3.  每个叶子节点都是黑色的空节点（NIL节点）；
4.  每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)；
5.  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点；
6.  每次新插入的节点都必须是红色。

这就是一个红黑树

![5ba3d87b5bf04abe9bcf6265e758d292.png][]

【[点击跳转 1.11Java-数据结构][1.11Java-]】更加详细的红黑树讲解

既然红黑树这么好，为什么不一直使用红黑树，而是数组长度大于64，同时链表长度大于8的情况下，链表将转化为红黑树？

红黑树在插入数据的时候需要通过左旋、右旋、变色这些操作来保持平衡，为了保持这种平衡是需要付出代价的。当链表很短的时候，没必要使用红黑树，否则会导致效率更低，当链表很长的时候，使用红黑树，保持平衡的操作所消耗的资源要远小于遍历链表锁消耗的效率，所以才会设定一个阈值

#### 1.12.3.2.6 数据覆盖  ####

**JDK1.8后，HashMap改用尾插法，解决了链表死循环问题，但是又会出现一个新的问题：数据覆盖**

JDK1.7中transfer函数负责数据的迁移，而JDK1.8直接在resize函数中完成了数据迁移，没有transfer函数。

我们来看一下put操作的源码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
     // 判断是否有hash碰撞---指定hashcode是否在桶中已有数据存储
            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;
        }

其中第六行代码是判断是否出现Hasn碰撞

两个线程A、B都进行put操作，并且hash函数计算出的hashode是相同的，当线程A执行完

if ((p = tab[i = (n - 1) & hash]) == null)//判断该hashcode是否在桶中已有数据

后（正准备插入数据时），由于时间片耗尽导致被挂起，而线程B得到时间片后在该处插入了元素，完成了正常的插入。然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全，造成数据覆盖。

避免HashMap发生死循环的常用解决方案：

1.  使用线程安全的**ConcurrentHashMap**替代HashMap，推荐
2.  使用线程安全的Hashtable替代，性能低，不推荐
3.  使用synchronized或者Lock加锁，会影响性能，不推荐

HashMap的死循环只发生在JDK1.7版本中  
主要原因：头插法+链表+多线程并发+扩容，累加到一起就会形成死循环

多线程下：建议采用ConcurrentHashMap替代  
JDK1.8，HashMap改用尾插法，解决了链表死循环问题，但是可能会丢失数据

JDK8引入红黑树：

解决查找效率问题

尾插法解决了死循环问题

#### 1.12.3.2.7 **HashMap 线程安全吗？** ####

我们进入HashMap的源码中，很显然，它所有的方法都没有synchrionzed关键字修饰，表明它线程是不安全的。

![19bc53ef92d54de48d26fc2e8d030bc6.png][]

![7a3aeedf5454451ba3aaee0561e23fc2.png][]

HashMap是线程不安全的，在多线程环境中不建议使用，应该使用ConcurrentHashMap，但是其线程不安全体现在什么地方？

HashMap的线程不安全有三个方面：**死循环**，**数据丢失**，**数据覆盖**。其中死循环和数据丢失在Java8中已经得到解决。

#### 1.12.3.2.8 **HashMap在java1.8和java1.7的区别** ####

**结构不同**

java1.7是数组+链表结构，java1.8中是数组+链表+红黑树

**插入方式不同**

java1.7采用的是头插法，java8采用的是尾插法。

java1.7先扩容在插入数据，java1.8是先插入数据后扩容

扩容时java1.7需要rehash，在java1.8中不需要重新计算hash值。HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。

### 1.12.3.3 HashTable ###

> 是较早使用的双列集合，HashMap是HashTable的替代，HashTable的key不允许为null，HashMap的key可以为null，但是只能有一个

如果在多线程环境下，可以使用 HashTable ， HashTable 中所有 CRUD 操作都是线程同步的，与此同时，线程同步的代价就是效率变低了。

HashTable是通过synchrionzed关键字实现线程安全的。

![23ecbb755dbf47fcad1446cb93dd34af.png][]

![0ea2af26395049ab88f04676f6890a96.png][]

### 1.12.3.4 ConcurrentHashMap ###

在Java 5 后，出现了线程安全的 HashMap——ConcurrentHashMap ，**支持高并发更新与查询的哈希表(基于HashMap）**， ConcurrentHashMap 相对于 HashTable 来说， ConcurrentHashMap 将 hash 表分为 16 个桶（默认值），诸如 get,put,remove 等常用操作只锁当前需要用到的桶。试想，原来只能一个线程进入，现在却能同时 16 个写线程进入（写线程才需要锁定，而读线程几乎不受限制，并发性的提升是显而易见。

在保证安全的前提下，进行检索不需要锁定。与hashtable不同，该类不依赖于synchronization去保证线程操作的安全。

### 1.12.3.5 LinkedHashMap ###

> HashMap下有个子类LinkedHashMap，存储数据采用的哈希表结构+链表结构。通过链表结构可以保证元素的存取顺序一致；通过哈希表结构可以保证的键的唯一、不重复，需要重写键的hashCode()方法、equals()方法。

集合是编程中最常用的数据结构。而谈到并发，几乎总是离不开集合这类高级数据结构的支持。比如两个线程需要同时访问一个中间临界区 (Queue)，比如常会用缓存作为外部文件的副本(HashMap)

<table style="width:397px;"> 
 <tbody> 
  <tr> 
   <td style="width:395px;"><a href="https://blog.csdn.net/qq_43757965/article/details/127436337" title="上一篇：1.11Java-数据结构" rel="nofollow">上一篇：1.11Java-数据结构</a></td> 
  </tr> 
  <tr> 
   <td style="width:395px;"><a href="https://blog.csdn.net/qq_43757965/article/details/127463123" title="下一篇：1.13Java-Iterator迭代器、增强for、迭代、递归" rel="nofollow">下一篇：1.13Java-Iterator迭代器、增强for、迭代、递归</a></td> 
  </tr> 
 </tbody> 
</table>

[1e7353eb6bbd43d584e829a54f3eecc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ad379514845e4485b6ab01efc16ec56b.png
[31b16660f7104713b458e6457f7042a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9e5103a55db34ab88f3af9ea3a1e497e.png
[2db1391b6240402ab3d3eab5ac809736.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fd4f251c066b42908d643537cbf21646.png
[2f04be9e267a4ea0af7f6598763273e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d73bc7c2257441e3b36ecbbb12e4f5ba.png
[51d98457273843fd835038e11ab1f2f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7e25cc54d5e44b19b36eaf760f77c418.png
[e73c982778704c29ba02aea463d7b9fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fa72c428ddf54b65817ec2b75a2742b4.png
[0410f18239064d1b9b084238b79f985a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/da56a4863e63439fab1be6e4c2b5a3ea.png
[f9eec283a143496484809e48e8fab127.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c1190113a65f4efbbfc67bec7c50fb05.png
[23_Java_HashSet_bilibili]: https://www.bilibili.com/video/BV1YA411T76k/?p=23&spm_id_from=333.880.my_history.page.click&vd_source=4460899c4c86d948fd7945bd9eb055df
[1cd254ea9f444b98a87f736460654275.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f4db6c6bdea34f4f9d772b35969aae1e.png
[171ffde446b746aca5771750f3cdeebc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8af5540302ba49ce88f5f6072df56dc1.png
[10da949ef2e042a387b132e5aaa49e5b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bf2e7e2fbfdb481683a0b08af1ce08f0.png
[ad7470e86de34edf84c360efd59d7f98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6971e1b2935d4371aa14b5bc3715cc77.png
[89ec1521f7164eb7896b76002d3a44fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/91d506b6a4124ea0a387f5162fdad6d1.png
[5ba3d87b5bf04abe9bcf6265e758d292.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7a20c39171b64cb48beeaaaf40f6de3e.png
[1.11Java-]: https://blog.csdn.net/qq_43757965/article/details/127436337?spm=1001.2014.3001.5502
[19bc53ef92d54de48d26fc2e8d030bc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/659b64798aa04479b19ced94ad6186b5.png
[7a3aeedf5454451ba3aaee0561e23fc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/310fd08707734f3b8a77a7efb748b4fc.png
[23ecbb755dbf47fcad1446cb93dd34af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/5c5a44cdd328459889337a947ab89096.png
[0ea2af26395049ab88f04676f6890a96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c6195af041ba464684b74a99189f0521.png