集合

集合

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的次幂？