本文主要是介绍Java集合详解(List、Map、Set)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Java集合详解

• 集合
• • 单列集合双列集合
  • ArrayList
  • HashMap
  • HashTable
• 解决hash冲突的方法
• • 开放地址法
  • 再hash法
  • 拉链法
  • 建立公共溢出区
• 常用的容器要点总结（list、map、set）
• HashMap的put存储过程
• List、Map、Set的区别
• ArrayList和LinkedList的区别
• HashMap、TreeMap和HashTable的区别

集合

单列集合双列集合

集合分为单列集合和双列集合，单列集合分为list，set；双列集合就是map；list分为ArrayList和LinkedList；set分为HashSet和TreeSet；map分为hashmap和treemap；我们常用的是ArrayList和HashMap。

ArrayList

ArrayList底层是数组，默认长度为0；当添加第一个元素时，长度变为10，扩容机制是当数组存满时，还要继续添加元素，就会创建一个新的数组，容量是之前数组的1.5倍，并把之前元素复制进新数组。

HashMap

HashMap1.7之前底层是数组+链表，1.8之后是数组+链表+红黑树，底层重写了hashcode和equals方法，先计算hash值，hash值会根据hash函数计算出索引值，存入指定位置，如果位置上没有，存入，如果有比较equals，如果相同，新值替换旧值，如果不同，就挂下面，链表长度大于等于8，转为红黑树，小于等于6，转成链表。扩容机制，默认是16，加载因子0.75，每次长度乘2。

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。
Entry是hashmap中的静态内部类

HashMap中关键属性
transient Entry[] table; // 存储元素的实体数组
transient int size;// 存放元素的个数
int threshold; // 临界值   当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量
final float loadFactor; // 加载因子
transient int modCount;// 被修改的次数

HashTable

HashTable和concurrenthashmap线程安全，hashtable所有的方法都是synchronized修饰的，concurrenthashmap1.7之后是CAS+synchronized，所以是线程安全的。

解决hash冲突的方法

hash碰撞冲突：hashCode()的方法是为了产生不同的hash值，但是当两个对象的hash一样时，就发生了碰撞冲突

我们常用的解决方法有四种：

1. 开放地址法
2. 再hash法
3. 拉链法
4. 建立公共溢出区

开放地址法

// 开放地址法：
基本思想：当发生地址冲突的时候，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止
所用公式 Hi(key) = [H(key) + di]mod m;其中i = 1、2、3…k（k<m-1）,H(key)为关键字key的直接hash地址；M为hash表的长度；
di为再次探测时的地址增量；根据di的不同取法，有不同的称呼；
线性探测再散列：di = 1、2、3、4…k (k<m-1)
二次探测再散列：di = 12,-12,22,-22…k2,-k2 (k<=m/2)
伪随机再散列：di = 伪随机数

再hash法

// 再hash法：
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。
缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止；

拉链法

// 拉链法：
在HashMap中 就是使用拉链法 来解决hash冲突的问题的；
将所有关键字为同义词的记录存储在同一线性链表中。
优点：

1. 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
2. 由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
3. 开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
4. 在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

缺点：
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

建立公共溢出区

// 建立公共溢出区：
建立公共溢出区的基本思想是：假设哈希函数的值域是[1,m-1]，则设向量HashTable[0…m-1]为基本表，每个分量存放一个记录，另外设向量OverTable[0…v]为溢出表，所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

常用的容器要点总结（list、map、set）

• ArrayList
  • 基于动态数组的数据结构
  • 随机访问快，增删慢
  • 占用内存少，每个索引的位置是实际的数据
  • 效率高，线程不安全
• LinkedList
  • 链表结构
  • 增删快，访问慢（数据多的情况下增删也不一定快）
  • 占用内存较多，每个节点中存储的是实际的数据和前后节点的位置
  • 线程不安全
• Vector
  • 效率低
  • 线程安全
• HashMap
  • HashMap是无序的
  • 方法不是同步的
  • 线程不安全
  • 效率较高
  • key value允许null值
  • HashMap的父类是AbstractMap
• HashTable
  • HashTable是无序的
  • 方法是同步的
  • 线程安全
  • 效率较低（Hashtable的所有 public 方法声明中都有 synchronized关键字，HashMap的源码中则没有）
  • key value不允许null值
  • Hashtable的父类是Dictionary
• TreeMap
  • TreeMap是有序的
  • 不能重复
  • 当未实现 Comparator 接口时，value可以为null，key 不可以为null，否则抛 NullPointerException 异常；
  • 当实现 Comparator 接口时，若未对 null 情况进行判断，则可能抛 NullPointerException 异常。如果针对null情况实现了，可以存入，但是却不能正常使用get()访问，只能通过遍历去访问
• HashSet
  • 底层数据结构是哈希表
  • 唯一、无序
  • 两个方法：hashCode()和equals()
• LinkedHashSet
  • 底层数据结构是链表和哈希表
  • 由链表保证元素有序、哈希表保证元素唯一
• TreeSet
  • 底层数据结构是红黑树
  • 自然排序、比较器排序
  • 根据比较的返回值是否是0来决定是否唯一
  • 唯一、有序

HashMap的put存储过程

1、hash(key)，取key的hashcode进行高位运算，返回hash值
2、如果hash数组为空，直接resize()
3、对hash进行取模运算计算，得到key-value在数组中的存储位置i
（1）如果table[i] == null，直接插入Node<key,value>
（2）如果table[i] != null，判断是否为红黑树p instanceof TreeNode。
（3）如果是红黑树，则判断TreeNode是否已存在，如果存在则直接返回oldnode并更新；不存在则直接插入红黑树，++size，超出threshold容量就扩容
（4）如果是链表，则判断Node是否已存在，如果存在则直接返回oldnode并更新；不存在则直接插入链表尾部，判断链表长度，如果大于8则转为红黑树存储，++size，超出threshold容量就扩容

1.8之前是头插法，1.8之后是尾插法

public V put(K key, V value) {
        // 如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
        // 此时threshold为initialCapacity 默认是1<<4(24=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
       // 如果key为null，存储位置为table[0]或table[0]的冲突链上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);// 对key的hashcode进一步计算，确保散列均匀
        int i = indexFor(hash, table.length);// 获取在table中的实际位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        // 如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;// 保证并发访问时，若HashMap内部结构发生变化，快速响应失败
        addEntry(hash, key, value, i);// 新增一个entry
        return null;
    }

List、Map、Set的区别

list有序，顺序是添加的顺序
set无序指的是打乱了插入的顺序，不能重复。HashSet底层是HashMap是真正的无序；TreeSet有序，但这个顺序是根据排序规则排序的（二叉树排序）
map是键值对

ArrayList和LinkedList的区别

LinkedList首部插入数据很快，因为只需要修改插入元素前后节点的prev值和next值即可

ArrayList首部插入数据慢，因为数组复制的方式移位耗时多

LinkedList中间插入数据慢，因为遍历链表指针（二分查找）耗时多

ArrayList中间插入数据快，因为定位插入元素位置快，移位操作的元素没那么多

LinkedList尾部插入数据慢，因为遍历链表指针（二分查找）耗时多

ArrayList尾部插入数据快，因为定位速度快，插入后移位操作的数据量少

HashMap、TreeMap和HashTable的区别

HashMap和HashTable是无序的，TreeMap是有序的（二叉树排序）
HashMap的方法不是同步的、线程不安全。Hashtable的方法是同步的、线程安全的；
HashMap效率较高，Hashtable效率较低
HashMap允许null值(key和value都允许)，HashTable不允许null值
父类不同：HashMap的父类是AbstractMap，Hashtable的父类是Dictionary

HashMap
在JDK1.7及之前，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个数组中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间

HashMap的实现原理：
首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。
当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中

这篇关于Java集合详解(List、Map、Set)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！