当前位置:网站首页 > Java基础 > 正文

java集合基础原理



集合框架

集合的底层原理 (上层建筑,"经济"基础)

一、HashMap底层

  1. HashMap底层原理?

HashMap存储的元素是key,value格式的。用的是数组加链表的结合,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的.在每个数组元素上都有一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上.jdk1.8之后,当链表长度大于8之后,将链表转为红黑树,以减少搜索时间

 

疑问:HashMap的值到底是怎么存储的?
解答:HashMap存的时候,先根据 Hash算法把key存储下来,具体方法是把key的值存储到对应的数组下标位置,当存放的位置发生了哈希碰撞,就把这个key放到数组下标对应的链表上面。我老是在想的是key,value,到底是咋存的,一直有疑惑。

  1. HashMap的长度设计?

为了能让HashMap存取高效,尽量减少碰撞,也就是尽量要把数据分配均匀.如果Hash映射得比较均匀松散,一般应用很难出现碰撞.但是Hash值的范围,长度是40亿.这样的数组,内存是无法放下的.因此,用之前需要对数组的长度取模运算,得到的余数才能用来存放的位置也就是对应的数组下标取余(%)操作中如果除数是2的幂次则等价于于其除数减1的与(&)操作.并且采用二进制位操作&,相对于%能够提高运算效率这就解释了HashMap的长度为什么是2的幂次方.

为啥是取模呢?定一个数组的长度,hash算法 结合完,可能就是这样的结果

  1. HashMap默认初始化长度为16,之后每次扩容,容量为原来的2倍,创建时如果给了初始值,会将其扩为2的n次幂(“数字其实都是2的次幂”)
  2. HashMap和HashTable的区别?
    线程是否安全:HashMap的非线程安全的,HashTable是线程安全的,HashTable内部的方法都经过synchronize修饰(如果要保证线程安全使用ConcurrentHashMap)
    效率:因为线程安全的问题,HashMap比HashTable效率高一点.HashTable已经被淘汰不被使用.
    对null key和null value的支持:HashMap中null可以作为键,这样的键只能有一个,可以有一个或者多个键对应的值为null.但是在HashTable中put进的键只要有一个是null,直接抛出NullPointerExcepiton
  3. ConcurrentHashMap和HashTable的区别?
    底层数据结构:

JDK1.7 ConcurrentHashMap 底层采分分段的数组+链表实现,JDK1.8 采用的数据结构是数组+链表/红黑二叉树.

Hashtable的底层数据结构是采用数组+链表的形式.

  1. 实现线程安全的方式:

HashTable使用的是同一把锁,效率非常低下.

 

二、HashSet底层原理

  1. HashMap和HashSet的区java集合基础原理别?
    如果你看过HashSet源码的话就应该知道:HashSet底层就是基于HashMap实现的.HashSet的源码非常非常少,因为除了clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外,其他方法都是直接调用HashMap 中的方法。

ol start="2">

  • HashSet如何检查重复?
  • blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    当你把对象加入HashSet时,HashSet会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的hashcode值做比较,如果没有相符的hashcode,HashSet会假设对象没有出现过,但是如果发现相同的hashcode值的对象,这时候会调用equals方法检查hashcode相等的对象是否真的相同.如果两者相同,HashSet就不会让其加入成功.

    hashCode()与equals()的相关规定:

    1. 如果两个对象相等,则hashcode一定也是相同的
    2. 两个对象相等,对两个equals方法法返回true
    3. 两个对象有相同的hashcode值,它们也不一定是相等的
    4. 综上,equals方法被覆盖过,则hashCode方法法也必须被覆盖
    5. hashCode()的默认行为是对堆上的对象产生独特值.如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据).

    ==与equals的区别

    1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
    2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较
    3. ==指引用是否相同 equals()指的是值是否相同

    /blockquote>

    三、ArrayList和LinkedList底层原理

    1. ArrayList和LinkedList的区别?
      是否保证线程安全:ArrayList和LinkedList都是不同步的,也就是不保证线程安全
      底层数据结构:ArrayList是Object数组,LinkedList是双向链表
      内存空间占用:ArrayList空间浪费主要体现在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存储直接前驱和直接后继以及数据)
    2. ArrayList和Vector的区别?为什么要用ArrayList取代Vector?
      Vector类的所有方法都是同步的.可以由两个线程安全的访问一个Vector对象,但是一个线程访问Vector的话,代码要在同步操作上面耗费大量的时间.
      ArrayList不是同步的,所以在不需要保证线程安全时建议使用ArrayList
    3. ArrayList和LinkedList是线程不安全的,多线程的情况需要使用哪个?

     
     

    Vector已经弃用了,不允许使用

    1. ArrayList的扩容机制?
      是拷贝一个新的扩容的数组,并将之前的值也拷贝过来 (HashMap的扩容一样)
      list集合说明:

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    ArrayList实现了RandomAcces接口,说明他具有快速访问功能,RandomAccess只是标识,并不是说ArrayList实现andomAccess接口才具有快速随机访问功能的

    /blockquote>

    四、

    集合的遍历

    1. 各种遍历方式的性能?
      传统的for循环遍历

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    基于计数器的,因为是基于元素的位置,按位置读取.所以我们可以知道,对于顺序存储,因为读取特定位置元素的平均时间复杂度是O(1),所以遍历整个集合的平均时间复杂度为O(n).而对于链式存储,因为读取特定位置元素的平均时间复杂度是O(n),所以遍历整个集合的平均时间复杂度为n的平方

    /blockquote>

    1. 迭代器遍历,Iterator

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    因为Iterator内部维护了当前遍历的位置,所以每次遍历,读取下一个位置并不需要从集合的第一个元素开始查找,只要把指针向后移一位就行了,这样一来,遍历整个集合的时间复杂度就降低为O(n);

    /blockquote>

    1. foreach循环遍历

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    分析Java字节码可知,foreach内部实现原理,也是通过Iterator实现的,只不过这个Iterator是Java编译器帮我们生成的,所以我们不需要再手动去编写.但是因为每次都要做类型转换检查,所以花费的时间比Iterator略长.时间复杂度和Iterator一样.

    /blockquote>

    1. 各遍历方式适用于什么场合?
      传统的for循环遍历,基于计数器的:

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    /blockquote>

    1. 迭代器遍历,Iterator:

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    /blockquote>

    1. foreach循环遍历:

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    foreach只是让代码更加简洁了,但是他有一些缺点,就是遍历过程中不能操作数据集合(删除等),所以有些场合不使用。 而且它本身就是基于Iterator实现的,但是由于类型转换的问题,所以会比直接使用Iterator慢一点,但是还好,时间复杂度都是一样所以怎么选择,参考上面两种方式,做一个折中的选择。

    /blockquote>

    1. 链表的大size的数据用什么遍历?

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    Iterator,千万不能选择普通for循环遍历,效率贼低

    /blockquote>

    1. 说说List,Set,Map三者的区别?
      List(对付顺序的好帮手): List接口存储一组不唯一(可以有多个元素引用相同的对象),有序的对象
      Set(注重独一无二的性质): 不允许重复的集合.不会有多个元素引用相同的对象.
      Map(用Key来搜索的专家): 使用键值对存储.Map会维护与Key有关联的值.两个Key可以引用相同的对象,但Key不能重复
    2. 集合框架底层数据结构总结

     
     

    1. 如何选用集合?

    blockquote style="margin-top: 5px; margin-bottom: 5px; padding-left: 1em; margin-left: 0px; border-left: 3px solid rgb(238, 238, 238); opacity: 0.6;">

    主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用Map接口下的集合,需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时,就选择实现Collection接口的集合,需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet,不需要就选择实现List接口的比如ArrayList或LinkedList,然后再根据实现这些接口的集合的特点来选用

    /blockquote>

     
     

    版权声明


    相关文章:

  • Java基础类型分为2025-04-23 12:42:03
  • java笔试基础方面2025-04-23 12:42:03
  • java线程基础总结2025-04-23 12:42:03
  • java基础差自学2025-04-23 12:42:03
  • 有java基础学python2025-04-23 12:42:03
  • java语言基础英文2025-04-23 12:42:03
  • java基础所有题型2025-04-23 12:42:03
  • java从基础开始2025-04-23 12:42:03
  • 面试java基础中级2025-04-23 12:42:03
  • java基础机构2025-04-23 12:42:03