hashset java 键值对_java集合全知道

集合相关知识

思维导图

总览

    java集合，也称作容器，主要是由两大接口派生出来的：Collection和Map

    其中Collection存放单一元素；Map存放key-value键值对

Collocation

Collection主要包含List、Queue和Set

List

允许重复、有序对象，可以插入null

ArrayList

• 有序、可重复

• 动态数组，空间多有浪费在预留

• 初始容量为10，扩容为1.5倍(向下取整)

• 查速度快，增删慢

• 线程不安全

LinkedList

• 有序、可重复

• 底层数据结构是双向链表(方便前后遍历)，查询慢，增删快

• 线程不安全，效率高，不支持高效的随机访问，空间大多浪费在存储前后驱上

• 由于没有扩容机制，使用双向链表来存储元素，所以插入和删除元素的效率很高

• 不具备随机访问的特点，查找元素只能从head或者tail指针一个个比较，所以查找中间的元素时效率很低。

• 查询优化，可以根据index是否大于一般的长度决定从头还是从尾寻找。

Vector(过时)

Object数组，被ArrayList代替，两倍的扩容导致消耗更好的内容

• 底层是数组，查询快，增删慢，线程安全

• 效率低

• 有序可重复，扩容为2n

使用推荐

• 改查多用ArrayList(增删在尾部也用)，遇事不决用ArrayList

• 增删多用LinkedList

Set

不允许重复，可以插入null、无序

每个Set底层实现都是对应的Map

数值放在map的key上，value上放了个PRESENT，是一个静态的Object，相当于place holder，每个key都指向这个object

HashSet

底层借助HashMap实现，其本质就是new一个HashMap

• 非同步、无序、唯一

• 允许元素为NULL、存取快

• 初始容量影响性能

    采用HashMap的key来存储元素，通过hashCode()和equals()来保证唯一性

LinkedHashSet

    继承了HashSet，其底层采用了HashMap+双线链表的实现。

• 迭代有序、允许为NULL、非同步

    这是一个HashSet+LinkedList的结构，特点是即拥有了O(1)的时间复杂度，又能保留插入的顺序

TreeSet

基于TreeMap实现的，存储元素是有序的。

• 非同步

• 常应用于对不重复的元素定制排序。

• 底层是红黑树(唯一、有序)自然排序和比较器排序来保证元素有序

• 其判重采用compareTo()方法是否返回0。

    采用红黑树结构，特点是有序，可以用自然排序或者自定义比较器来排序；缺点是查询的速度没有HashSet快

Queue&Deque

Queue是一端进另一端出的线性数据结构。

Deque是两端都可以进入的。

Queue

一般来说都是先进先出的，但是PriorityQueue按照。

其方法有两组API，实现的功能一样只是一组会抛出异常一组会返回特殊值

Deque

Deque是两端都可以进出，每端都有两组，一组抛异常，一组返回特殊值

实现类

LinkedList、ArrayDeque、PriorityQueue

• 想实现普通队列-先进先出，就使用LinkedList或者ArrayDeque

• 想实现优先队列，就使用PriorityQueue

• 想实现栈，就使用ArrayDeque

ArrayDeque和LinkedList

• ArrayDeque是一个扩容的数组，LinkedList是链表结构

• ArrayDeque中不能存null，而LinkedList可以存null

• ArrayDeque在操作头尾端的增删操作更加高效，LinkedList只有在当要删除中间某个且已经找到了这个元素后的移除才是O(1)的

• ArrayDeque在内存使用方面更加高效。

Map

    使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复。每个键只能映射一个值

HashMap

• 实现原理

  • 由数组和链表组成，其中数组是hashmap的主体，而链表是为了解决哈希冲突而存在的。

  • 是Hashtable的轻量级实现

• 无序、不安全、效率高、key和value都允许null

• 默认初始容量为16，每次扩容为2n

• 链表长度大于阈值8是将链表转为红黑树

HashTable(过时)

    HashTable底层的存储结构是数组+链表，是一个线程安全的集合，但是效率低下，而且会长时间锁住HashTable，所以淘汰了。

• 无序，线程安全、方法是同步的、效率低

• 不允许null

• 默认初始容量为11，扩容为2n+1

LinkedHashMap

可以看做是HashMap和LinkedList的结合

• 继承自HashMap的双向链表

• 迭代有序、非同步

利用LinkedHashMap可以实现LRU缓存淘汰策略

• 指定accessOrder=true可以设置链表按照访问顺序访问，通过提供的构造器可以设定accessOrder

• 重写removeEldestEntry()方法，内部定义逻辑，通常是判断容量是都达到了上限，如是则执行淘汰

TreeMap

    TreeMap是SortedMap的子类，具有排序功能，基于红黑树实现。默认情况下按照key自然排序，或者是通过传入定制的Comparator进行自定义规则排序

• 有序、非线程安全

• 基于红黑树

总结

ArrayList和vector的异同

• 共同点

  • 都实现了List接口，都是有序集合，底层实现都是数组，可以按照位置的索引号取出某个元素，允许元素重复和为NULL

• 区别

  • 同步性：

    • ArrayList是非同步的

    • vector是同步的，但是效率极低

  • 扩容大小

    • vector增长为原来的两倍

    • ArrayList增长为原来的1.5倍

HashMap和HashTable的异同

• 共同点：都是Map接口

• 区别：

  • 同步性：

    • HashMap是非同步的，线程不安全

    • HashTable是同步的，线程安全

  • 是否允许为NULL

    • HashMap允许为NUll

    • HashTable不允许为null

  • contain方法

    • HashMap没有，而是使用containsValue和containsKey

    • HashTable还是有Contain方法的

  • 继承不同：

    • HashMap继承自AbstractMap

    • Hashtable继承自Dictionary

Itrator和Listlterator的异同

• 相同点：都是迭代器，当需要对集合中元素进行遍历而不需要干涉其遍历过程时，都可以使用

• 区别;

  • 使用范围不同：

    • Itrator：应用于所有的集合

    • ListIterator：只能用于List及其子类

  • 是否可以添加元素

    • Iterator：不能添加对象

    • ListIterator：可以向List中添加对象

  • 遍历能力不同

    • Iterator：可以顺序向后遍历，不能顺序向前遍历

    • ListIterator：即可以顺序向后遍历，也可以顺序向后遍历

ArrayDeque和LinkedList

• ArrayDeque是一个可扩容的数组，LinkedList是链表结构

• ArrayDeque不能存null值，LinkedList可以存null值

• ArrayDeque在操作头尾的增删操作时更加高效，LinkedList只有当要移除中间某个元素且已经找到这个元素后移除才是O(1)

• ArrayDeque在内存使用方面更高效

综上所述，只要不是必须要存null就使用ArrayDeque

最后

• 如果觉得看完有收获，希望能给我点个赞，这将会是我更新的最大动力，感谢各位的支持

• 欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我

• 如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。