深圳市住房城乡建设局网站,搜狗推广下架,网页设计期末作业源码,网站建设南昌看的博客里面总结的线程的八股文
1、线程安全的集合有哪些#xff1f;线程不安全的呢#xff1f;
线程安全的#xff1a; Hashtable#xff1a;比HashMap多了个线程安全。 ConcurrentHashMap:是一种高效但是线程安全的集合。 Vector#xff1a;比Arraylist多了个同步化…看的博客里面总结的线程的八股文
1、线程安全的集合有哪些线程不安全的呢
线程安全的 Hashtable比HashMap多了个线程安全。 ConcurrentHashMap:是一种高效但是线程安全的集合。 Vector比Arraylist多了个同步化机制。 Stack栈也是线程安全的继承于Vector。
线性不安全的 HashMap Arraylist LinkedList HashSet TreeSet TreeMap
2、Arraylist与 LinkedList 异同点 是否保证线程安全 ArrayList 和 LinkedList 都是不同步的也就是不保证线程安全 底层数据结构 Arraylist 底层使用的是Object数组LinkedList 底层使用的是双向循环链表数据结构 插入和删除是否受元素位置的影响 ArrayList 采用数组存储所以插入和删除元素的时间复杂度受元素位置的影响。 比如执行 add(E e) 方法的时候 ArrayList 会默认在将指定的元素追加到此列表的末尾这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话 add(int index, E element) 时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 LinkedList 采用链表存储所以插入删除元素时间复杂度不受元素位置的影响都是近似 O1而数组为近似 O(n)。 是否支持快速随机访问 LinkedList 不支持高效的随机元素访问而ArrayList 实现了RandmoAccess 接口所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) 方法)。 内存空间占用 ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间因为要存放直接后继和直接前驱以及数据。
3、ArrayList 与 Vector 区别 Vector是线程安全的ArrayList不是线程安全的。其中Vector在关键性的方法前面都加了synchronized关键字来保证线程的安全性。如果有多个线程会访问到集合那最好是使用Vector因为不需要我们自己再去考虑和编写线程安全的代码。 ArrayList在底层数组不够用时在原来的基础上扩展0.5倍Vector是扩展1倍这样ArrayList就有利于节约内存空间。
4、说一说ArrayList 的扩容机制
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化并将原有数组内容复制到新数组中去。
默认情况下新的容量会是原容量的1.5倍。
以JDK1.8为例说明:
public boolean add(E e) {//判断是否可以容纳e若能则直接添加在末尾若不能则进行扩容然后再把e添加在末尾ensureCapacityInternal(size 1); // Increments modCount!!//将e添加到数组末尾elementData[size] e;return true;}
/* 每次在add()一个元素时arraylist都需要对这个list的容量进行一个判断。通过
ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力经过处理之后
将元素存储在数组elementData的尾部*/
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {modCount;
/* 若ArrayList已有的存储能力满足最低存储要求则返回add直接添加元素如果最低要求的
存储能力ArrayList已有的存储能力这就表示ArrayList的存储能力不足因此需要调用 grow();方法
进行扩容*/if (minCapacity - elementData.length 0)grow(minCapacity);
}
private void grow(int minCapacity) {// 获取elementData数组的内存空间长度int oldCapacity elementData.length;// 扩容至原来的1.5倍int newCapacity oldCapacity (oldCapacity 1);//校验容量是否够if (newCapacity - minCapacity 0)newCapacity minCapacity;//若预设值大于默认的最大值检查是否溢出if (newCapacity - MAX_ARRAY_SIZE 0)newCapacity hugeCapacity(minCapacity);// 调用Arrays.copyOf方法将elementData数组指向新的内存空间//并将elementData的数据复制到新的内存空间elementData Arrays.copyOf(elementData, newCapacity);
}5、Array 和 ArrayList 有什么区别什么时候该应 Array而不是 ArrayList 呢 Array 可以包含基本类型和对象类型ArrayList 只能包含对象类型。 Array 大小是固定的ArrayList 的大小是动态变化的。 ArrayList 提供了更多的方法和特性比如addAll()removeAll()iterator() 等等。
6、HashMap的底层数据结构是什么
在JDK1.7 和JDK1.8 中有所差别
在JDK1.7 中由“数组链表”组成数组是 HashMap 的主体链表则是主要为了解决哈希冲突而存在的。
在JDK1.8 中由“数组链表红黑树”组成。当链表过长则会严重影响 HashMap 的性能红黑树搜索时间复杂度是 O(logn)而链表是糟糕的 O(n)。因此JDK1.8 对数据结构做了进一步的优化引入了红黑树链表和红黑树在达到一定条件会进行转换 当链表超过 8 且数据总量超过 64 才会转红黑树。 将链表转换成红黑树前会判断如果当前数组的长度小于 64那么会选择先进行数组扩容而不是转换为红黑树以减少搜索时间。 7、解决hash冲突的办法有哪些HashMap用的哪种
解决Hash冲突方法有:开放定址法、再哈希法、链地址法拉链法、建立公共溢出区。HashMap中采用的是 链地址法 。 开放定址法也称为 再散列法 基本思想就是如果 pH(key) 出现冲突时则以 p 为基础再次hash p1H§ ,如果p1再次出现冲突则以p1为基础以此类推直到找到一个不冲突的哈希地址 pi 。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素而且因为存在再次hash所以 只能在删除的节点上做标记而不能真正删除节点。 再哈希法(双重散列多重散列)提供多个不同的hash函数当 R1H1(key1) 发生冲突时再计算 R2H2(key1) 直到没有冲突为止。 这样做虽然不易产生堆集但增加了计算的时间。 链地址法(拉链法)将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。 建立公共溢出区将哈希表分为公共表和溢出表当溢出发生时将所有溢出数据统一放到溢出区。
8、为什么在解决 hash 冲突的时候不直接用红黑树而选择先用链表再转红黑树?
因为红黑树需要进行左旋右旋变色这些操作来保持平衡而单链表不需要。当元素小于 8 个的时候此时做查询操作链表结构已经能保证查询性能。当元素大于 8 个的时候 红黑树搜索时间复杂度是 O(logn)而链表是 O(n)此时需要红黑树来加快查询速度但是新增节点的效率变慢了。
因此如果一开始就用红黑树结构元素太少新增效率又比较慢无疑这是浪费性能的。
9、HashMap默认加载因子是多少为什么是 0.75不是0.6 或者 0.8
回答这个问题前我们来先看下HashMap的默认构造函数
int threshold; // 容纳键值对的最大值
final float loadFactor; // 负载因子
int modCount;
int size;Node[] table的初始化长度length(默认值是16)Load factor为负载因子(默认值是0.75)threshold是HashMap所能容纳键值对的最大值。threshold length * Load factor。也就是说在数组定义好长度之后负载因子越大所能容纳的键值对个数越多。
默认的loadFactor是0.750.75是对空间和时间效率的一个平衡选择一般不要修改除非在时间和空间比较特殊的情况下 如果内存空间很多而又对时间效率要求很高可以降低负载因子Load factor的值 。 相反如果内存空间紧张而对时间效率要求不高可以增加负载因子loadFactor的值这个值可以大于1。
追溯下作者在源码中的注释JDK1.7
As a general rule, the default load factor (.75) offers a good tradeoff between
time and space costs. Higher values decrease the space overhead but increase the
lookup cost (reflected in most of the operations of the HashMap class, including
get and put). The expected number of entries in the map and its load factor
should be taken into account when setting its initial capacity, so as to
minimize the number of rehash operations. If the initial capacity is greater
than the maximum number of entries divided by the load factor, no rehash
operations will ever occur.翻译过来大概的意思是作为一般规则默认负载因子0.75在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销但提高查找成本体现在大多数的HashMap类的操作包括get和put。设置初始大小时应该考虑预计的entry数在map及其负载系数并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子rehash操作将不会发生。
10、HashMap 的put方法流程
以JDK1.8为例简要流程如下 首先根据 key 的值计算 hash 值找到该元素在数组中存储的下标 如果数组是空的则调用 resize 进行初始化 如果没有哈希冲突直接放在对应的数组下标里 如果冲突了且 key 已经存在就覆盖掉 value 如果冲突后发现该节点是红黑树就将这个节点挂在树上 如果冲突后是链表判断该链表是否大于 8 如果大于 8 并且数组容量小于 64就进行扩容如果链表节点大于 8 并且数组的容量大于 64则将这个结构转换为红黑树否则链表插入键值对若 key 存在就覆盖掉 value。
