集合
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的次幂?