Java集合详解(List、Map、Set)

简介: Java集合详解(List、Map、Set)

集合

单列集合双列集合

集合分为单列集合和双列集合

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

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一样时,就发生了碰撞冲突

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

  • 开放地址法
  • 再hash法
  • 拉链法
  • 建立公共溢出区

开放地址法

开放地址法:

基本思想:当发生地址冲突的时候,按照某种方法继续探测哈希表中的其他存储单元,直到找到空位置为止

所用公式 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,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

缺点:

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


建立公共溢出区

建立公共溢出区:

建立公共溢出区的基本思想是:假设哈希函数的值域是[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.8之前,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个数组中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。

JDK1.8及之后,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间

HashMap的实现原理:

首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中


目录
相关文章
|
3月前
|
存储 缓存 JavaScript
Set和Map有什么区别?
Set和Map有什么区别?
258 1
|
4月前
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些?
for...of循环在遍历Set和Map时的注意事项有哪些?
263 121
|
7月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
176 2
|
4月前
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器,其允许通过键值快速的索引到对应的元素。在unordered_set中,元素的值同时也是唯一地标识它的key。在内部,unordered_set中的元素没有按照任何特定的顺序排序,为了能在常数范围内找到指定的key,unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快,但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
184 0
|
4月前
|
编译器 C++ 容器
用一棵红黑树同时封装出map和set
再完成上面的代码后,我们的底层代码已经完成了,这时候已经是一个底层STL的红黑树了,已经已符合库里面的要求了,这时候我们是需要给他穿上对应的“衣服”,比如穿上set的“衣服”,那么这个穿上set的“衣服”,那么他就符合库里面set的要求了,同样map一样,这时候我们就需要实现set与map了。因此,上层容器map需要向底层红黑树提供一个仿函数,用于获取T当中的键值Key,这样一来,当底层红黑树当中需要比较两个结点的键值时,就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
47 0
|
4月前
|
存储 编译器 容器
set、map、multiset、multimap的介绍及使用以及区别,注意事项
set是按照一定次序存储元素的容器,使用set的迭代器遍历set中的元素,可以得到有序序列。set当中存储元素的value都是唯一的,不可以重复,因此可以使用set进行去重。set默认是升序的,但是其内部默认不是按照大于比较,而是按照小于比较。set中的元素不能被修改,因为set在底层是用二叉搜索树来实现的,若是对二叉搜索树当中某个结点的值进行了修改,那么这棵树将不再是二叉搜索树。
201 0
|
5月前
|
安全 Java API
【Java性能优化】Map.merge()方法:告别繁琐判空,3行代码搞定统计累加!
在日常开发中,我们经常需要对Map中的值进行累加统计。}else{代码冗长,重复调用get()方法需要显式处理null值非原子操作,多线程下不安全今天要介绍的方法,可以让你用一行代码优雅解决所有这些问题!方法的基本用法和优势与传统写法的对比分析多线程安全版本的实现Stream API的终极优化方案底层实现原理和性能优化建议一句话总结是Java 8为我们提供的Map操作利器,能让你的统计代码更简洁、更安全、更高效!// 合并两个列表});简单累加。
452 0
|
7月前
|
人工智能 Java
Java 中数组Array和列表List的转换
本文介绍了数组与列表之间的相互转换方法,主要包括三部分:1)使用`Collections.addAll()`方法将数组转为列表,适用于引用类型,效率较高;2)通过`new ArrayList&lt;&gt;()`构造器结合`Arrays.asList()`实现类似功能;3)利用JDK8的`Stream`流式计算,支持基本数据类型数组的转换。此外,还详细讲解了列表转数组的方法,如借助`Stream`实现不同类型数组间的转换,并附带代码示例与执行结果,帮助读者深入理解两种数据结构的互转技巧。
363 1
Java 中数组Array和列表List的转换
|
8月前
|
编译器 容器
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set