Java集合-HashMap向

Java集合-HashMap向

1. 集合框架

集合框架图

List(单列,有序可重复):

  • List接口扩展自Collection,它可以定义一个允许重复的有序集合,从List接口中的方法来看,List接口主要是增加了面向位置的操作,允许在指定位置上操作元素

    • ArrayList:基于数组;数组增删慢,查找快。因为每次增删都要创建新的数组,但数组有索引。
      • 底层原理:它是用数组存储元素的,这个数组可以动态创建,如果元素个数超过了数组的容量,那么就创建一个更大的新数组,并将当前数组中的所有元素都复制到新数组中。
    • Vector:基于数组,线程安全的,效率低
    • LinkedList:基于链表;链表增删快,查找慢。因为每个元素存储本身内存地址的同时还存储下一个元素的地址。

Set(单列,不可重复):

  • Set接口扩展自Collection,它与List的不同之处在于,规定Set的实例不包含重复的元素。在一个规则集内,一定不存在两个相等的元素。

    • 散列集HashSet:存储的元素无序,不可重复,底层是哈希表,可以使用它的无参构造方法来创建空的散列集,也可以由一个现有的集合创建散列集。在散列集中,有两个名词需要关注,初始容量和客座率。客座率是确定在增加规则集之前,该规则集的饱满程度,当元素个数超过了容量与客座率的乘积时,容量就会自动翻倍。
      • 链式散列集LinkedHashSet:存储的元素有序,不可重复,底层是哈希表和链表的结合
    • 树形集TreeSet:树形集是一个有序的Set,其底层是一颗树,这样就能从Set里面提取一个有序序列了。在实例化TreeSet时,我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。
    • Queue:队列是一种先进先出的数据结构,元素在队列末尾添加,在队列头部删除。Queue接口扩展自Collection,并提供插入、提取、检验等操作。
System.out.println(set.first()); // 输出第一个元素
System.out.println(set.lower(3333)); //小于3333的最大元素
System.out.println(set.higher(2222)); //大于2222的最大元素
System.out.println(set.floor(3333)); //不大于3333的最大元素
System.out.println(set.ceiling(3333)); //不小于3333的最大元素
System.out.println(set.pollFirst()); //删除第一个元素
System.out.println(set.pollLast()); //删除最后一个元素

Map(双列集合):

  • HashMap:非线程安全,高效,支持null

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

    • LinkedHashMap:是HashMap的子类,保存了记录的插入顺序
  • HashTable:线程安全,低效,不支持null

  • TreeMap:能够将它保存的记录根据键排序,默认键值升序排序,

其它集合类:

  • ConcurrentHashMap:什么是ConcurrentHashMap?
  • CopyOnWriteArrayList:
    1. 它最适合于具有以下特征的应用程序:List大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突
    2. 支持高效率并发且是线程安全的
    3. 因为通常需要复制整个基础数组,所以可变操作(add(),set()和remove()等等)的开销很大
    4. 迭代器支持hasNext(),next()等不可变操作,但不支持可变remove()等操作
    5. 使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照

2. HashMap

HashMap怎么put和get值的?

PUT

  • a. 计算key的hashcode
  • b. 根据hashcode计算出需要将该键值对存储的位置-即桶的位置
  • c. 找到桶的位置后,如果桶未被占用,则存入该键值对;若桶中已有数据,则需要遍历桶中数据,并且比较key的equals方法。遇到key相同的,则用新的value,把旧值替换掉(put操作会将旧值覆盖掉)。若没找到,则将该键值对存储在链表的末尾。

GET

  • a. 计算key的hashcode
  • b. 根据hashcode,定位该元素所在桶的位置
  • c. 若桶为空,则返回null;若桶不空,则遍历桶中数据,比较key的equals方法,若遇到相同的元素,则返回对于的value中;没遇到,则返回null

什么是Hash碰撞?解决的方法有哪些?

  1. 基本概念
    哈希算法:根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。
    哈希表:数据经过哈希算法之后得到的集合。这样关键字和数据在集合中的位置存在一定的关系,可以根据这种关系快速查询。
    非哈希表:与哈希表相对应,集合中的 数据和其存放位置没任何关联关系的集合。

由此可见,哈希算法是一种特殊的算法,能将任意数据散列后映射到有限的空间上,通常计算机软件中用作快速查找或加密使用。

哈希冲突:由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。

  1. 解决哈希冲突的方法
    解决哈希冲突的方法一般有:开放定址法、链地址法(拉链法)、再哈希法、建立公共溢出区等方法。

key相同,Value不同,如何存储?

  • key不动,Value替换

什么时候扩容,如何扩容?

  1. HashMap默认的负载因子为0.75,当一个map填满75%的bucket,调用addEntry方法

  2. 扩容:创建一个新的Entry空数组,长度是原数组的2倍。

  3. ReHash:遍历原Entry数组,把所有的Entry重新Hash到新数组。

  4. HashMap的两种遍历方式

  • entrySet().iterator();(效率高,推荐使用)
  • keySet().iterator();

HashMap的HashCode()和equals()

  • Object.equals方法,如果每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。

  • 于是,Java采用了哈希表的原理。哈希算法也称为散列算法,当集合要添加新的元素时,将对象通过哈希算法计算得到哈希值(正整数),然后将哈希值和集合(数组)长度进行&运算,得到该对象在该数组存放的位置索引。如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了;如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就表示发生冲突了,在HashMap中,HashCode冲突时,他们会存储在同一个bucket位置的链表中,再利用equals方法进行比较,如果不同,则在链表中使用头插法插入一个元素。

  • 这样一来,实际调用equals方法比较的次数就大大降低了,几乎只需要一两次。

  • 简而言之,在集合查找时,hashcode能大大降低对象比较次数,提高查找效率!

高并发下的HashMap会产生的情况

  • 高并发场景下调用transfer方法,可能会出现环形链表,导致程序死循环

HashMap与HashTable

  • HashMap性能高,HashTable性能低
  • HashMap是非synchronized,HashTable线程安全
  • HashMap可以接受null的键和值,HashTable不可以

3. ConcurrentHashMap(JDK 1.7)

segment:

  1. 一个segment就是一个HashMap对象,读写操作高度自治,segment之间互不影响
  2. segment的写入是需要上锁的,因此对同一segment的并发写入会被阻塞

get方法:

  1. 为输入的key做hash运算,得到hash值
  2. 通过hash值,定位到对应的segment对象
  3. 再次通过hash值,定位到segment当中数组的具体位置

put方法:

  1. 为输入的key做hash运算,得到hash值
  2. 通过hash值,定位到对应的segment对象
  3. 获取可重入锁
  4. 再次通过hash值,定位到segment当中数组的具体位置
  5. 插入或覆盖hashEntry对象
  6. 释放锁

ConcurrentHashMap的锁分段技术

  • HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁,假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。
  • segment是一种可重入锁,在ConcurrentHashMap里扮演锁的角色。

ConcurrentHashMap的读是否要加锁,为什么

  • ConcurrentHashMap读不加锁,写只加部分锁。在多线程下得高性能读写用比较好。

ConcurrentHashMap的迭代器是强一致性的迭代器还是弱一致性的迭代器

  • 弱一致性迭代器

4. Q&A

Q:集合、数组、泛型的关系,并比较

  • 数组
    在分配空间上,数组分配在一块连续的数据空间上,因此在分配空间时必须确定大小。

    • 数组优点:
         1. 可以利用偏移地址来访问元素,效率高
         2. 可以使用折半方法查找元素,效率较高

    • 数组缺点:
         1. 空间连续,存储效率低;
         2. 插入和删除元素效率比较低,且比较麻烦

  • 集合

    • 和数组相比,使用大小根据保存的元素数确定,定义时不用确定大小。增加、删除、访问数组中的数据时也比较方便。
    • 但集合不是类型安全的。使用集合元素时,需要拆装箱,相对于简单的赋值而言,拆装箱需要进行大量的计算。对值类型进行装箱时,必须分配并构造一个全新的对象。其次,拆箱所需的强制转换也需要进行大量的计算。总之,带来了很大的性能消耗。
  • 泛型

    • 集合中,任何引用或值类型都将隐式地向上强制转换为Object。如果项是值类型,添加到列表中时,进行装箱操作,在检索时进行取消装箱操作。这样,强制转换以及装箱和拆箱操作都会降低性能。

    • 另一个限制是缺少编译时类型检查。同一个集合可接收不同类型,所有项都强制转换为 Object,在编译时无法检查是否可以收这种类型,还是人为错误输入了另一个类型,同时智能感应只会提示Object的方式,使得检查错误变得艰难。

    • 如果我们对其中的类型进行一些限制,使之成为统一的类型,虽然稍微增加了编码的复杂性,但好处是可以创建一个 更安全并且速度更快的列表, 校验错误也变得容易。

    • 鉴于这种情况,催生了泛型的产生。

    • 泛型通常使用List(of   T)形式,List是类型(或者类)的名称 ,字母T是点位符类似于参数。它表示 必须提供一个用来定制泛型的特定类型值,同时也限定的它只能是这个类型。

    • 泛型有两种形式:泛型类型和泛型方法

      1. List(of  T)是泛型类型,定义了完整的类型或类的模板。
        泛型 方法是一种方法模板,使用时必须指明方法使用的“具体类型”。
      2. 格式:方法名(of T)(参数)

Q: 对比Vector、ArrayList、LinkedList有何区别?

  • 这三者都是实现集合框架中的 List,也就是所谓的有序集合,因此具体功能也比较近似,比如都提供按照位置进行定位、添加或者删除的操作,都提供迭代器以遍历其内容等。但因为具体的设计区别,在行为、性能、线程安全等方面,表现又有很大不同。
  • Vector 是 Java 早期提供的线程安全的动态数组,如果不需要线程安全,并不建议选择,毕竟同步是有额外开销的。Vector 内部是使用对象数组来保存数据,可以根据需要自动的增加容量,当数组已满时,会创建新的数组,并拷贝原有数组数据。
  • ArrayList 是应用更加广泛的动态数组实现,它本身不是线程安全的,所以性能要好很多。与 Vector 近似,ArrayList 也是可以根据需要调整容量,不过两者的调整逻辑有所区别,Vector 在扩容时会提高 1 倍,而 ArrayList 则是增加 50%。
  • LinkedList 顾名思义是 Java 提供的双向链表,所以它不需要像上面两种那样调整容量,它也不是线程安全的。

Q: 对比Hashtable、HashMap、TreeMap有什么不同?

  • Hashtable 是早期 Java 类库提供的一个哈希表实现,本身是同步的,不支持 null 键和值,由于同步导致的性能开销,所以已经很少被推荐使用。
  • HashMap 是应用更加广泛的哈希表实现,行为上大致上与 HashTable 一致,主要区别在于 HashMap 不是同步的,支持 null 键和值等。通常情况下,HashMap 进行 put 或者 get 操作,可以达到常数时间的性能,所以它是绝大部分利用键值对存取场景的首选,比如,实现一个用户 ID 和用户信息对应的运行时存储结构。
  • TreeMap 则是基于红黑树的一种提供顺序访问的 Map,和 HashMap 不同,它的 get、put、remove 之类操作都是 O(log(n))的时间复杂度,具体顺序可以由指定的 Comparator 来决定,或者根据键的自然顺序来判断。

Q:如何解决Hash冲突?

Q: 如何保证集合是线程安全的? ConcurrentHashMap如何实现高效地线程安全?

  • 具体保证线程安全的方式,包括有从简单的 synchronize 方式,到基于更加精细化的,比如基于分离锁实现的 ConcurrentHashMap 等并发实现等。具体选择要看开发的场景需求,总体来说,并发包内提供的容器通用场景,远优于早期的简单同步实现。
    1. 为什么需要 ConcurrentHashMap?Hashtable 本身比较低效,因为它的实现基本就是将 put、get、size 等各种方法加上“synchronized”。简单来说,这就导致了所有并发操作都要竞争同一把锁,一个线程在进行同步操作时,其他线程只能等待,大大降低了并发操作的效率。
    1. ConcurrentHashMap如何实现高效地线程安全?put加锁通过分段加锁segment,一个hashmap里有若干个segment,每个segment里有若干个桶,桶里存放K-V形式的链表,put数据时通过key哈希得到该元素要添加到的segment,然后对segment进行加锁,然后在哈希,计算得到给元素要添加到的桶,然后遍历桶中的链表,替换或新增节点到桶中size分段计算两次,两次结果相同则返回,否则对所有段加锁重新计算

Q:HashMap是有序的吗?如何实现有序?

  • HashMap不是有序的,使用TreeMap可以实现有序;

Q:hashcode()的作用,与equal()有什么区别?

hashcode()的作用:

  • 对象equals方法参与运算的自身属性attr不能被修改,并且同一个对象的hashCode值任何时候的返回值都应该相等;
  • hashCode不等的两个对象equals一定不相等,但是hashCode相等的两个对象equals不一定相等;
  • 根据规定,重写对象的equals方法必须重写hashCode方法,尽管不写也能通过编译;

equal()的区别:

  • hashCode主要用于提升查询效率,来确定在散列结构中对象的存储地址;
  • 重写equals()必须重写hashCode(),二者参与计算的自身属性字段应该相同;
  • hash类型的存储结构,添加元素重复性校验的标准就是先取hashCode值,后判断equals();
  • equals()相等的两个对象,hashcode()一定相等;
  • 反过来:hashcode()不等,一定能推出equals()也不等;
  • hashcode()相等,equals()可能相等,也可能不等。