集合

集合

List 和 Set 区别

  • List 可以重复,set不可以,list有序,set有的实现类是无序的

  • List 实现类:

    • ArrayList:提供了使用索引的随意访问,底层是数组,线程不安全

      • new的时候capacity是0 ,add的时候加载默认 capacity 10
    • LinkedList:提供了添加删除的便捷操作,底层是链表,

    • Vector:可实现自动增长的对象数组。表示底层数组,线程安全

      • elementData 是"Object[]类型的数组",它保存了添加到Vector中的元素。elementData是个动态数组,如果初始化Vector时,没指定动态数组的>大小,则使用默认大小10。随着Vector中元素的增加,Vector的容量也会动态增长,capacityIncrement是与容量增长相关的增长系数,具体的增长方式,请参考源码分析中的ensureCapacity()函数。

      • elementCount 是动态数组的实际大小。

      • capacityIncrement 是动态数组的增长系数。如果在创建Vector时,指定了capacityIncrement的大小;则,每次当Vector中动态数组容量增加时>,增加的大小都是capacityIncrement。

  • set实现类

    • Set集合判断元素是否是同一个使用的是equals方法
    • HashSet:调用该对象的hashCode()方法来得到该对象的hashCode值,然后根据 hashCode值来决定该对象在HashSet中存储位置
    • LinkedHashSet:集合同样是根据元素的hashCode值来决定元素的存储位置,但是它同时使用链表维护元素的次序。当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素。 LinkedHashSet在迭代访问Set中的全部元素时,性能比HashSet好,但是插入时性能稍微逊色于HashSet。
    • TreeSet:是SortedSet接口的唯一实现类,底层的数据结构是红黑树,TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式,自然排序 和定制排序。
      • 自然排序:使用要排序元素的CompareTo(Object obj)方法来比较元素之间大小关系,然后将元素按照升序排列。
      • 定制排序:应该使用Comparator接口,实现 int compare(T o1,T o2)方法。
  • 相互转换:

    • 因为List和Set都实现了Collection接口的addAll(Collection<? extends E> c)方法,因此可以采用addAll()方法将List和Set互相转换;另外,List和Set也提供了Collection<? extends E> c作为参数的构造函数,因此通常采用构造函数的形式完成互相转化。

List 和 Map的区别

  • 存储特点:

    • list是存储单列数据的集合,map是存储键和(key,value)}这样的双列数据的集合,List 中存

    储的数据是有顺序,并且允许重复;Map 中存储的数据是没有顺序的,其键是不能重复的,

    它的值是可以有重复的。

ArrayList和LinkedList和Vector区别

  • ArrayList:

    • 线程不安全,(没有在添加元素的地方加锁,会有值覆盖和数组越界的情况发生)。
    • 属性信息:capacity:默认是10 (new的时候,长度是0,add元素后读取默认长度)。
    • 扩容:
      • 条件:长度不够的时候。
      • 扩容后,长度为原来长度的 1.5倍。
    • 底层是数组,优势是便利,劣势是修改元素。占用内存是连续的。
  • LinkedList:

    • 线程不安全的,(添加元素时倒数第二个指向后一个的元素会被最后一次覆盖,造成丢失),(操作数modCount和expectmodCount不等)
    • 属性信息:仅仅是指针的指向,不存在capacity
    • 表面上实现了list,背地里还是一个队列。
    • 底层书双向链表,优势修改新增快,便利慢。不依赖连续内存空间。
  • ArrayList主要控件开销在于需要在lList列表预留一定空间;而LinkList主要控件开销在于需要存储结点信息以及结点指针信息

  • Vector:线程安全

    • Vector与ArrayList一样,也是通过数组实现的,不同的是它支持线程的同步,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比访问ArrayList慢。
    • 扩容时长度为原来的两倍

HashMap 和HashTable的区别

  • HashMap:
    • 不是线程安全的,可以允许null key 和null value。
  • HashTable
    • 线程安全的,不可以允许null key 也不可以有 null value。

HashSet 和 HashMap区别

  • hashmap 存储的时键值对,hashset存储的是对象
  • 使用hashset的时候,最好优先重写 hashcode 和 equals

HashMap和Concurrent HashMap的区别

  • ConcurrentHashMap对整个桶数组进行了分段,而HashMap则没有

  • ConcurrentHashMap在每一个分段上都用锁进行保护,从而让锁的粒度更精细一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。

HashMap的工作原理及代码实现

  • 容量和负载因子:容量的默认大小是 16,负载因子是 0.75

  • 内部包含了一个 Entry 类型的数组 table。HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

  • 哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。(jdk8中链表为8时转为红黑树存储,长度低于6转回来)

  • 扩容为原来的2倍大小。

  • 简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好

  • 在常规构造器中,没有为数组table分配内存空间(有一个入参为指定Map的构造器例外),而是在执行put操作的时候才真正构建table数组。

  • capacity一定是 2的次幂

    为何HashMap的数据长度一定是2的次幂?

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,378评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,356评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,702评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,259评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,263评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,036评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,349评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,979评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,469评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,938评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,059评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,703评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,257评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,262评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,501评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,792评论 2 345

推荐阅读更多精彩内容

  • 什么是集合 集合框架:用于存储数据的容器。 集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。 任何集合...
    Java__JJ阅读 262评论 0 1
  • Java集合类可用于存储数量不等的对象,并可以实现常用的数据结构如栈,队列等,Java集合还可以用于保存具有映射关...
    小徐andorid阅读 1,918评论 0 13
  • 文章目录集合容器概述什么是集合集合的特点集合和数组的区别使用集合框架的好处常用的集合类有哪些?List,Set,M...
    灬佐手边阅读 340评论 0 1
  • 原文地址 Java集合 Java集合框架:是一种工具类,就像是一个容器可以存储任意数量的具有共同属性的对象。 Ja...
    gyl_coder阅读 973评论 0 8
  • Java集合框架,数据结构 所有的集合类位于 jdk下的 rt.jar 包下java.util下; 1、所有集合类...
    kaixingdeshui阅读 313评论 0 0