作一个网站要多少钱,网站建设陕西,wordpress文章大纲插件,网站建设中 html免费介绍一下常见的list实现类#xff1f;
ArrayList
线程不安全#xff0c;内部是通过数组实现的#xff0c;继承了AbstractList#xff0c;实现了List#xff0c;适合随机查找和遍历#xff0c;不适合插入和删除。排列有序#xff0c;可重复#xff0c;当容量不够的时候…介绍一下常见的list实现类
ArrayList
线程不安全内部是通过数组实现的继承了AbstractList实现了List适合随机查找和遍历不适合插入和删除。排列有序可重复当容量不够的时候会将原容量增加50%即乘以1.5。
LinkedList
LinkedList 是用链表结构存储数据的线程不安全。很适合数据的动态插入和删除随机访问和遍历速度比较慢增删快。另外他还提供了 List 接口中没有定义的方法专门用于操作表头和表尾元素可以当作堆栈、队列和双向队列使用。底层使用双向链表数据结构。
Vector数组实现、线程同步
Vector 与 ArrayList 一样也是通过数组实现的Vector和ArrayList用法上几乎相同但Vector比较古老一般不用。Vector是线程同步的效率低。即某一时刻只有一个线程能够写 Vector避免多线程同时写而引起的不一致性但实现同步需要很高的花费因此访问它比访问 ArrayList 慢。默认扩展一倍容量。
ArrayList初始容量是多少
ArrayList 默认的初始容量是 10。意味着当你创建一个新的 ArrayList 而不指定其容量时它会以一个内部数组长度为 10 的数组来开始。当添加的元素数量超过这个初始容量时ArrayList 的内部数组会进行扩容通常是增长为原来的 1.5 倍。
ArrayList是如何扩容的
1.一个新的ArrayList对象时它通常会分配一个初始容量为10。
2.当向ArrayList中添加一个新元素并且该元素的数量超过当前数组的容量时,就会触发扩容操作
3.扩容公式:newCapacity oldCapacity (oldCapacity 1)这实际上是将原容量增加50%即乘以1.5。
4、扩容过程创建一个新的数组其长度为新计算的容量。将原数组中的所有元素复制到新数组中。将ArrayList的内部引用从原数组更新为新数组。将新元素添加到新数组的末尾。
ArrayList的添加与删除元素为什么慢
ArrayList的添加与删除操作慢主要是因为其内部实现基于数组而数组在插入和删除元素时需要移动其他元素来保证连续性和顺序性这个过程需要耗费较多的时间。
java容器有哪些
ArrayList如何保证线程安全
1.借助锁:可以通过在访问 ArrayList 的代码块上使用 synchronized 关键字来手动同步对 ArrayList 的访问。这要求所有访问 ArrayList 的代码都知道并使用相同的锁。
2.使用 Collections.synchronizedList
聊聊常见set类都有哪几种
HashSet
HashSet线程不安全基于哈希表实现具有快速的插入、删除和查找操作。不保证元素的迭代顺序允许null元素的存在但只能有一个null元素。
LinkedHashSet
LinkedHashSet是HashSet的子类基于哈希表和双向链表实现可以维护元素的插入顺序。相比于 HashSet 增加了顺序性因此当需要保持元素插入顺序时可以选择使用LinkedHashSet。
TreeSet
TreeSet线程不安全基于红黑树实现不允许null值存在可以对元素进行自然排序或自定义排序。可以实现元素按照升序进行排序。
常见set的使用场景
HashSet适用于需要快速查找的场景不保证元素的顺序。
LinkedHashSet适用于需要保持元素插入顺序的场景。
TreeSet适用于需要元素排序的场景。
HashSet如何实现线程安全
使用Collections.synchronizedSet
Java 提供了一个简单的方法来创建一个同步的集合通过Collections.synchronizedSet方法。这个方法返回一个线程安全的集合包装器。使用这个方法后所有对集合的访问都将是同步的。
使用ConcurrentHashMap
如果需要更高效的并发访问可以使用ConcurrentHashMap来实现类似HashSet的功能。
手动同步
如果你不想使用上述任何一种方法也可以手动同步HashSet的访问。可以使用synchronized关键字来保护对HashSet的访问
介绍一下HashMap
HashMap主要是用于存储键值对。基于哈希表实现提供了快速的插入、删除和查找操作线程不安全的允许一个 null 键或多个 null 值。
不记录映射的顺序。
主要方法
put(K key, V value)将指定的值与该映射中的指定键关联。
get(Object key)返回指定键所映射的值。
remove(Object key)如果存在一个键的映射则将其从映射中移除。
size()返回此映射中的键值映射关系的数量。
HashMap怎么计算hashCode的
HashMap使用键的hashCode()方法来生成哈希值并对其进行一些处理以提高哈希表的性能和均匀分布。
生成hashcode为什么要使用扰动函数
目的提高哈希码的质量使其在哈希表中更均匀地分布。
扰动算法的步骤如下
1. 获取键的哈希码h key.hashCode()
2. 右移 16 位h 16
3. 异或运算h ^ (h 16)
这种方法通过将高位和低位的哈希码混合在一起减少了哈希冲突的概率从而使得哈希码更加均匀地分布在哈希表的桶中。
HashMap的主要参数都有哪些
初始容量
初始容量是HashMap在创建时分配的桶数组的大小。默认初始容量是 16。可以在创建HashMap时通过构造函数指定初始容量。
负载因子Load Factor
负载因子默认负载因子是 0.75这意味着当HashMap中的条目数达到当前容量的 75% 时HashMap会进行扩容。负载因子越低哈希表中的空闲空间越多冲突越少但空间利用率也越低。
阈值Threshold
阈值是HashMap需要扩容的临界点计算方式为初始容量 * 负载因子。当实际存储的键值对数量超过这个阈值时HashMap会进行扩容。
桶Bucket
HashMap内部使用一个数组来存储链表或树在 Java 8 及之后的版本中当链表长度超过一定阈值时会转化为树。每个数组元素称为一个桶bucket。哈希值经过计算后决定了键值对存储在哪个桶中。
哈希函数Hash Function
HashMap使用哈希函数将键的哈希码转换为数组索引。Java 的HashMap使用了扰动函数perturbation function来减少哈希冲突。
链表和树Linked List and Tree
在桶中的键值对存储方式上HashMap使用链表来处理哈希冲突。在 Java 8 及之后的版本中当链表的长度超过阈值默认是 8时链表会转换为红黑树以提高查找效率。
红黑树转换阈值Treeify Threshold
这是一个阈值当单个桶中的链表长度超过这个值时链表会转换为红黑树。默认值是 8。
扩容因子Resize Factor
当HashMap的大小超过阈值时容量会加倍。即新的容量是旧容量的两倍。
迭代器Iterators
HashMap提供了键、值和条目的迭代器用于遍历HashMap中的元素。
为什么hashMap的容量扩容时一定是2的幂次?
在HashMap中初始化设置长度时容量自动转成 2 的幂次长度这样设计有几个重要原因主要是为了优化性能和简化计算。
减少哈希冲突
哈希冲突发生时不同的键计算出的索引相同导致它们被存储在同一个桶中。通过将容量设置为2的幂次哈希表能够更均匀地分布哈希值减少冲突。
简化扩容
HashMap在需要扩容时通常会将容量加倍。如果容量总是2的幂次那么加倍后的容量仍然是2的幂次这样可以简化扩容过程中的计算和重新哈希操作。
内存对齐和效率
计算机内存分配通常更高效地处理 2 的幂次大小的内存块。使用 2 的幂次长度可以更好地利用内存对齐提高内存访问效率。
解决hash碰撞的方法
链地址法Chaining
在这种方法中每个桶bucket包含一个链表。当发生哈希碰撞时新的键值对被添加到相应桶的链表中。
线性探测Linear Probing
当发生哈希碰撞时线性探测法在哈希表中向后依次查找下一个空闲位置。
二次探测Quadratic Probing
二次探测法在发生哈希碰撞时按照平方序列查找空闲位置如 1, 4, 9, 16, ...。
双重散列Double Hashing
双重散列法使用两个不同的哈希函数。当第一个哈希函数发生碰撞时使用第二个哈希函数计算新的索引。
再哈希法Rehashing
再哈希法在发生碰撞时使用不同的哈希函数重新计算哈希值直到找到空闲位置。
HashMap的负载因子初始值为什么是0.75?
HashMap的负载因子load factor初始值设为 0.75 是一个经过权衡的结果主要考虑了性能和内存使用之间的平衡。
HashMap扩容过程怎么解决哈希冲突
HashMap 扩容过程
1. 当添加元素时如果数组为空会进行初始化默认情况下会创建一个长度为 16 的数组并且加载因子默认为 0.75。
2. 当数组中的元素数量大于或等于数组长度与加载因子的乘积时例如当数组长度为16加载因子为0.75并且元素数量达到12时16*0.75 12会触发扩容。扩容时数组长度会翻倍通常是2的幂并重新哈希所有元素到新的数组中。
哈希冲突解决
1. 链表法链表或红黑树在 HashMap 中每个位置索引可以存储一个链表或红黑树当链表长度超过一定阈值时。当发生哈希冲突时新的元素会被添加到对应的链表中。在 Java 8 及之后的版本中当链表长度达到 8 且数组长度大于 64 时链表会转换为红黑树以优化性能。
2. 哈希函数为了降低哈希冲突的概率HashMap 使用了一个哈希函数来计算键的哈希值。这个哈希函数考虑了键对象的哈希码以及键在数组中的索引位置通过一些位运算得到最终的哈希值。这样可以确保哈希值的分布尽可能均匀减少冲突的可能性。
3. 初始容量和加载因子初始容量和加载因子也会影响哈希冲突的概率。较大的初始容量和较小的加载因子可以降低哈希冲突的概率但也会增加空间开销。因此在选择这些参数时需要根据具体需求进行权衡。
为什么hashmap多线程会进入死循环
1、并发修改导致的链表环
当两个或多个线程同时修改HashMap例如在同一个桶中插入元素可能会导致链表的指针被错误地更新。
2、扩容导致的并发问题
HashMap在容量达到一定阈值时会进行扩容即重新分配桶数组并重新哈希所有键值对。如果在扩容过程中有其他线程同时进行插入操作可能会导致重新哈希过程中的数据不一致进而引发死循环。
3、解决方案
使用线程安全的数据结构在多线程环境中使用ConcurrentHashMap代替HashMap。ConcurrentHashMap通过分段锁机制来保证线程安全并发性能更好。
什么是HashTable?
Hashtable很多映射的常用功能与 HashMap类似不同的是它承自 Dictionary 类单线程并且是线程安全的。日常不建议使用。
什么是LinkedHashMap?
1. 有序性LinkedHashMap保证了键值对的顺序可以是插入顺序默认或访问顺序可选。
2. 哈希表和链表结合LinkedHashMap通过哈希表实现快速的键值对查找同时通过双向链表维护顺序。
3. 允许null键和值LinkedHashMap允许一个null键和多个null值。
4. 线程不安全LinkedHashMap不是线程安全的如果需要在多线程环境中使用需要通过外部同步机制来保证线程安全。
linkedHashMap为什么能用来做LRUCache缓存
LinkedHashMap 能用来做 LRU 缓存的关键原因在于它可以维护访问顺序并且通过重写removeEldestEntry方法可以轻松实现缓存的自动清理。
实现 LRU 缓存的步骤
1. 创建一个LinkedHashMap实例并将accessOrder参数设置为true。
2. 重写removeEldestEntry方法以便在缓存大小超过预定义的最大容量时自动移除最老的键值对。
linkedhashmap如何保证有序性
1. 双向链表LinkedHashMap在内部维护了一个双向链表。每个节点对应一个键值对并且包含指向前一个节点和后一个节点的引用。通过这个链表LinkedHashMap可以快速地遍历所有键值对保持其有序性。
2. 插入顺序默认情况下LinkedHashMap按照键值对插入的顺序来维护顺序。每次插入新键值对时它会将新节点添加到链表的末尾。
3. 访问顺序如果在构造方法中将accessOrder参数设置为trueLinkedHashMap将按照访问顺序来维护键值对的顺序。每次访问get或put操作一个键值对时它会将对应的节点移动到链表的末尾。
什么是fail-fast机制
在Java集合框架中fail-fast是一种机制用于检测在遍历集合时的结构性修改并立即抛出异常以防止不一致状态。fail-fast迭代器在检测到集合在迭代过程中被修改后会抛出ConcurrentModificationException异常。
