集合(常见面试题) (HashMap算法优化)

集合(常见面试题) (HashMap算法优化)

数组/链表

数组(查询快 , 新增, 删除慢)

链表(查询慢, 新增,删除快 )

Collection (单列)(接口)(java.util)

常用方法

  1. c .add 新增一个元素, 返回值是固定 true
  2. c. clear 清空集合所有元素
  3. c.contains 判断集合中是否存在这个元素
  4. c.iterator 获取集合的迭代器
    • iterator . next 获取下一个元素
    • iterator . hasNext 判断是否有下一个元素

List (可重复)(接口)

  • 有序集合/可以存储重复元素
  • 并发修改异常
    • 在用迭代器遍历集合时,不允许新增或者删除元素.新增或者修改后,再次调用next时,就会抛出并发修改异常.
    • 避免此异常的方法 : 用for循环遍历集合,不用迭代器遍历.
  • 列表迭代器: ListIterator .继承自Iterator
    • 列表迭代器可以从任一方向遍历集合.
    • 提供上一个/下一个方法.
    • 可以新增或者移除元素. 需要用列表迭代器提供的add方法.
  • 增强for循环 , 其实底层是一个迭代器.
  • ArrayList (实现类)
    • 底层数据结构是数组: 查询快 , 增删慢.
  • LinkedList (实现类)
    • 底层数据结构是链表: 增删快,查询慢
    • 特有功能:
      • 针对头尾的操作,获取/新增/删除 等.

Set (不可重复)

  • 底层是hashcode, 对集合的迭代顺序不做任何保证. 即每次遍历顺序都不一定一致.
    • hashcode特点
      • 同一个对象的hashcode的值是一致的
      • 默认情况下, 不同对象的hashcode不相同,但是通过方法重写, 是可以获得相同的hashcode.
  • 遍历的方式:
    • 增强for
    • 迭代器
  • HashSet(实现类)
    • 底层数据结构是hash表
      • 数组 + 链表实现
      • 默认长度为16
      • 通过hashcode 计算对象在hash表中的位置 :
        • hashcode 对数组长度取模. 即除数组长度的余数.
  • HashSet保证元素唯一性的源码分析
    • 先初始化hash表
    • 根据插入对象的hash值计算对象的存储位置
    • 如果该位置没有元素就存储元素.如果该位置有元素.
    • 将两个元素先进行hash值比较
    • 如果hash值不同,将元素添加到集合(也保存到hash表同样的位置)
    • 如果hash值相同. 再次调用对象的equals()方法进行比较该位置的所有元素,如果不同,将元素添加到集合.
  • LinkedHashSet(有序不重复)
    • 底层数据结构是hash表和链表
      • 链表决定了迭代器中元素插入的顺序.
      • hash表决定了元素不重复.
  • TreeSet(实现类)(有序不可重复)
    • 元素是有序的. 默认是是根据元素的自然排序进行排序.也可以通过构造方法设置比较器排序.
    • 自然排序 : 并不是按照元素添加顺序进行排序, 比如数字是根据从小到大的顺序进行排序的.
      • 被自然排序的对象必须实现自然排序接口 Comparable,不然会抛出异常.
      • 重写Cpmparable接口中的cpmparaTo()方法, 本方法如果return 0 ; 则认为返回的重复元素.如果返回正数则是认为在后面, 如果是负数则是认为在前面.
    • 根据指定的比较器进行排序
      • new TreeSet ( new Comparator )

Map (双列)

  • HashMap(实现类)
    • put() 新增元素put 方法, 后面赋值会覆盖之前的赋值.
    • remove() 根据key移除元素,并返回vaule, 没有这个key时返回null
    • keySet() 获取map中所有key的集合,用于map遍历
  • HashMap底层的数据结构是什么样的？
    • 底层最核心的数据结构是数组。
    • map是长度可变的，但是数组是有固定长度的,所以map也是动态扩容.
  • hash算法的优化
    • 先取到key的hash值32位， 然后将二进制计算后的结果，向右移动16位，左数前16位用0补全。
    • 然后将hashcode和右移16位之后的hashcode进行亦或运算。高低16位算法。
    • 亦或运算后的结果再转换成一个32位的int值 则是这个key的hash值。
    • 寻址算法 ： 上面得到的hash值进行‘与’运算 （n - 1）& hash
      • &运算 相同则为1 ， 不同则是0
      • 核心：前16位是固定的，无需参与&运算，只有后16位实际进行了计算。
    • 计算后得到数组长度的一位位置。
  • 为什么要如此优化数组寻址的过程？有什么优势？
    • 因为取模运算性能较差，为了优化这个寻址算法，采用如上算法，得到的效果一样。
  • 算法优化总结 ：
    • hash算法的优化 ：
      • 对每个hash值，在低16位之中，让高低16位进行亦或，保留了高低16位的特征，尽量避免了hash值后续出现冲突，防止大家进入相同位置。
    • 寻址算法的优化：
      • 用与&运算替代了 取模运算，提升了性能。
  • HashMap是如何解决hash冲突？
    • 如果经过取址算法计算后的值还是一致的。
    • 此时底层会在这个数组的位置，挂一个链表，将多个key-value同时放在数组的一个位置里。
    • get时， 会找到这个链表，遍历这个链表，取出value。
    • 如果链表过长，会把链表转化成红黑树。
  • HsahMap是如何进行扩容的
    • 2倍扩容。默认是16位。 -> 32位数组。
    • 扩容的时候 ，会重新进行寻址运算。之前的链表有可能会分开。
  • map集合的遍历
    • 方式1 : 获取keySet , 遍历set , 获取到每个key , 通过可以获取value
    • 方式2 : 获取所有键值对对象的集合 entrySet() ,获取Map.Entry 获取到键值。

Collections集合 工具类

常用方法

  • sort 指定list 按照升序排序
  • reverse 指定list 反转元素顺序
  • shuffle 重新随机排列元素顺序 (模拟洗牌)

哪些容器的线程安全的?

Vector

HashTable

HashTable 是线程安全的 , 这是他和HashMap的最大不同点 , 他的线程安全 , 在于在读写操作的时候都是synchronized .