win2003 建设网站,WordPress文件夹插件,51电子网,网站建设尢首先金手指Map接口和Collection接口是所有集合框架的父接口#xff1a; Collection接口的子接口包括#xff1a;Set接口和List接口 Map接口的实现类主要有#xff1a;HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等 Set接口的实现类主要有#xff1a;HashSet、Tr…Map接口和Collection接口是所有集合框架的父接口 Collection接口的子接口包括Set接口和List接口 Map接口的实现类主要有HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等 Set接口的实现类主要有HashSet、TreeSet、LinkedHashSet等 List接口的实现类主要有ArrayList、LinkedList、Stack以及Vector等 List接口及其实现
ArrayList 基于动态数组实现 允许快速随机访问元素 插入和删除操作可能需要移动其他元素因此在中间位置插入和删除的时间复杂度为O(n) 非同步不是线程安全的可以使用使用Collections.synchronizedList(new ArrayList()) 创建一个同步的 ArrayList。
LinkedList 基于双向链表实现 允许快速插入删除元素 不能快速随机访问访问元素的时间复杂度为On 非同步不是线程安全的。可以使用 Collections.synchronizedList(new LinkedList()) 创建一个同步的 LinkedList。 可以用做队列或双向队列 依赖于两个节点一个头节点一个尾节点 常用方法 添加 add(E e)在链表后添加一个元素 通用方法 addFirst(E e)在链表头部插入一个元素 特有方法 addLast(E e)在链表尾部添加一个元素 特有方法 删除 removeFirst(E e)删除头获取元素并删除 特有方法 removeLast(E e)删除尾 特有方法 查看 getFirst()获取第一个元素 特有方法 getLast()获取最后一个元素 特有方法 Stack 基于Vector实现代表了后进先出 是同步的是线程安全的 push入栈、peek查看栈顶元素、pop出栈、empty是否为空、size获取数目
Vector 基于动态数组实现类似于ArrayList 同步的是线程安全的 是需要线程安全的动态数组是使用但是通常使用ArrayList和Collections.syschronizedList来代替 Set接口及其实现类
set其实一直在用map那一套 public class HashSetE extends AbstractSetE implements SetE, Cloneable, java.io.Serializable {private transient HashMapE,Object map;private static final Object PRESENT new Object();public HashSet() {map new HashMap();}public boolean add(E e) {return map.put(e, PRESENT) null;}// Other methods delegate to the underlying map}
HashSet 元素存储HashSet 将元素添加到底层的 HashMap 中键是元素的哈希码值是一个占位符对象。HashSet的实现是基于HashMap的他使用HashMap来存储元素在HashSet中元素被当作HashMap的键而HashMap的值则是一个固定的占位符通常是 PRESENT 对象一个静态内部类对象。这样做是为了节省空间因为 HashSet 只关心元素的唯一性不需要存储额外的值。 去重HashSet 使用了 HashMap 键的唯一性来确保 HashSet 中不会有重复的元素。 不保证集合的迭代顺序顺序可能会随时间变化。 方法委派HashSet 的许多方法如 add、remove、contains 等都是通过调用底层 HashMap 的对应方法来实现的。 性能由于 HashSet 是基于 HashMap 实现的所以其性能与 HashMap 类似添加、删除和查找操作的平均时间复杂度为 O(1)。 允许存储null值。 LinkedHashSet
LinkedHashSet 是 HashSet 的一个子类它继承了 HashSet 的特性并且保持了元素的插入顺序。下面是关于 LinkedHashSet 的一些关键点 继承自HashSet并且使用链表维护元素的插入顺序 保证迭代顺序与插入顺序一致 允许存储null值。 插入、删除、和查找操作的时间复杂度为O(1)。
实现细节 当你向 LinkedHashSet 添加元素时它会使用 LinkedHashMap 来存储元素。 每个元素被当作 LinkedHashMap 的键值则是一个固定的占位符对象。 LinkedHashSet 通过委派 LinkedHashMap 来实现其 add、remove 和 contains 等方法。 TreeSet
TreeSet 是 Java 中实现 SortedSet 接口的一个集合类它基于 TreeMap 实现并且元素是按照自然顺序或通过提供的比较器排序的。以下是 TreeSet 的一些关键点 基于红黑树自平衡二叉搜索树实现 元素是有序的元素按照自然顺序或通过Comparator指定的顺序排 不允许存储null值会抛出NullPointerException 插入、删除、和查找操作的时间复杂度为O(log n)。 Map接口及其实现类
HashMap 基于哈希表实现调用put方法值首先将kv封装到Node对象中然后底层会调用k的hashCode方法得到hash值。根据这个值来决定到底该插入数组下标的哪个位置如果有两个值的哈希值一样就会调用equals方法进行比较如果哈希值一样但是不相等就会形成链表插入 如果相等那么相等的这个节点的value将会被覆盖。如果没有元素占用位置就直接放入即可。通过数组加链表形式 在Java8对hashmap进行了优化如果相同哈希值链表的长度超过8就从链表转换成红黑树。第一次添加元素的时候默认初期长度为16当往map中继续添加元素的时候通过hash值跟数组长度取“与”来决定放在数组的哪个位置如果出现放在同一个位置的时候优先以链表的形式存放在同一个位置的个数又达到了8个代码是7,从0开始及第8个开始判断是否转化成红黑树如果数组的长度还小于64的时候则会扩容数组。如果数组的长度大于等于64的话才会将该节点的链表转换成树。在扩容完成之后如果某个节点的是树同时现在该节点的个数又小于等于6个了则会将该树转为链表只有当数据量大于64才会有红黑树链表 HashMap内部结构是数组Node[] table和链表结合组成的复合结构数组被分成一个个桶bucket或槽通过哈希值决定键值对在这个数组的寻址哈希值相同的键值对则以链表形式存储。当链表大小超过阈值TREEIFY_THRESHOLD 8时链表就会被改造成树形结构。查询效率变高 Java8不再像Java7中那样需要满足两个条件Java8中扩容只需要满足一个条件当前存放新值注意不是替换已有元素位置时的时候已有元素的个数大于等于阈值已有元素等于阈值下一个存放后必然触发扩容机制且扩容发生在存放后即是数据存放后先存放后扩容判断当前存入对象的个数如果大于阈值则进行扩容。 允许存储null键和null值。 插入、删除、和查找操作的时间复杂度为O(1)。 非同步不是线程安全的。
LinkedHashMap 通过hashmap跟双向链表实现可以确保按照插入顺序迭代链表 遍历性能 与普通的HashMap相比在迭代LinkedHashMap时性能更加稳定。因为它不需要遍历整个桶而是按照链表顺序遍历元素。 实现方式 在内部实现上LinkedHashMap在每个条目中保留了前一个和后一个条目的引用以实现双向链表。这使得在插入、删除和遍历元素时的性能表现良好。
TreeMap 基于红黑树实现 键按照自然顺序或通过Comparator指定的顺序排序。 不允许存储Null键 插入、删除、和查找操作的时间复杂度为O(log n)。 Hashtable 也是使用哈希表还有链表实现 同步的是线程安全的。 不允许存储null键和null值。 插入、删除、和查找操作的时间复杂度为O(1)。
Properties 继承自Hashtable表示一个持久化的属性集。 每个键及其对应值都是一个字符串。 常用于读取和写入配置文件。 ConcurrentHashMap 不允许存储null键和null值。 插入、删除、和查找操作的时间复杂度为O(1)。 在多线程环境下使用HashMap进行put操作时存在丢失数据的情况为了避免这种bug的隐患强烈建议使用ConcurrentHashMap代替HashMap。 HashTable是一个线程安全的类它使用synchronized来锁住整张Hash表来实现线程安全即每次锁住整张表让线程独占相当于所有线程进行读写时都去竞争一把锁导致效率非常低下。ConcurrentHashMap可以做到读取数据不加锁并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小允许多个修改操作并发进行其关键在于使用了锁分段技术。它使用了多个锁来控制对hash表的不同部分进行的修改。
分段锁Segment Locking机制
早期版本的ConcurrentHashMapJava 7及之前使用分段锁机制具体如下 ConcurrentHashMap内部将整个哈希表分为多个段Segment每个段都是一个独立的哈希表并拥有自己的锁。 这种机制允许多个线程同时访问不同段的元素从而提高并发度。 ConcurrentHashMap 为了提高本身的并发能力在内部采用了一个叫做 Segment 的结构一个 Segment 其实就是一个类 Hash Table 的结构Segment 内部维护了一个链表数组我们用下面这一幅图来看下 ConcurrentHashMap 的内部结构,从下面的结构我们可以了解到ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作第一次 Hash 定位到 Segment第二次 Hash 定位到元素所在的链表的头部因此这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可不会影响到其他的 Segment这样在最理想的情况下ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作刚好这些写操作都非常平均地分布在所有的 Segment上所以通过这一种结构ConcurrentHashMap 的并发能力可以大大的提高。 CAS操作和分段锁
在Java 8中ConcurrentHashMap使用了一种新的机制结合了CASCompare-And-Swap操作和细粒度的分段锁。 使用CAS操作来保证对单个节点的原子性操作减少锁的使用。 在插入、删除和更新操作中如果CAS操作失败即另一个线程同时修改了相同的位置则退而使用锁进行操作。 在Java 8中ConcurrentHashMap取消了分段锁的概念直接在哈希桶bucket级别进行锁定使用CAS操作和synchronized块来保证并发安全。这使得数据结构更加简单且操作更加直观。 为了优化哈希冲突情况下的查找性能Java 8引入了红黑树。当链表的长度超过一定阈值默认是8时链表会转换为红黑树。这样在高冲突情况下查找操作的时间复杂度从O(n)降到了O(log n)极大地提高了性能。 CAS 操作通过比较当前值与预期值如果两者相等则更新为新值否则重试该操作。
数据结构
ConcurrentHashMap在Java 8中的内部数据结构有以下几个关键组成部分 数组NodeK,V[] table哈希表的核心数组存储链表或红黑树的头节点。 链表和红黑树数组中的每个桶bucket最初是一个链表。当链表长度超过阈值8时链表会转换为红黑树以提高查询效率。
