网站设计上海,潍坊最新通知,电子科技公司网站网页设计,网站购买空间ArrayList底层的实现原理是什么
底层数据结构
ArrayList底层是用动态的数组实现的
初始容量
ArrayList初始容量为0#xff0c;当第一次添加数据的时候才会初始化容量为10
扩容逻辑
ArrayList在进行扩容的时候是原来容量的1.5倍#xff0c;每次扩容都需要拷贝数组 添加逻… ArrayList底层的实现原理是什么
底层数据结构
ArrayList底层是用动态的数组实现的
初始容量
ArrayList初始容量为0当第一次添加数据的时候才会初始化容量为10
扩容逻辑
ArrayList在进行扩容的时候是原来容量的1.5倍每次扩容都需要拷贝数组 添加逻辑
确保数组已使用长度size加1之后足够存下下一个数据.
计算数组的容量如果当前数组已使用长度1后的大于当前的数组长度则调用grow方法扩容原来的1.5倍
确保新增的数据有地方存储之后则将新元素添加到位于size的位置上。
返回添加成功布尔值。
ArrayList listnew ArrayList(10)中的list扩容几次
该语句只是声明和实例了一个 ArrayList指定了容量为 10未扩容
如何实现数组和List之间的转换
数组转List
String[] strs {aaa,bbb,ccc};
ListString list Arrays.asList(strs);
List转数组 ListString list new ArrayListString();list.add(aaa);list.add(bbb);list.add(ccc);String[] array list.toArray(new String[list.size()]);
用Arrays.asList转List后如果修改了数组内容list受影响吗
修改了数组的内容list会受影响因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合在这个集合的构造器中把我们传入的这个集合进行了包装而已最终指向的都是同一个内存地址
List用toArray转数组后如果修改了List内容数组受影响吗
修改了list内容数组不会影响当调用了toArray以后在底层是它是进行了数组的拷贝跟原来的元素就没啥关系了所以即使list修改了以后数组也不受影响
ArrayList 和 LinkedList 的区别是什么
底层数据结构
ArrayList 是动态数组的数据结构实现
LinkedList 是双向链表的数据结构实现
操作数据效率 查找时间复杂度都是O(n) 新增和删除时间复杂度是O(n)
内存空间占用
ArrayList底层是数组内存连续节省内存
LinkedList 是双向链表需要存储数据和两个指针更占用内存
线程安全
都不是线程安全的
在方法内使用局部变量则是线程安全的
使用线程安全的ArrayList和LinkedList
ListObject syncArrayList Collections.synchronizedList(new ArrayList());
ListObject syncLinkedList Collections.synchronizedList(new LinkedList());二叉搜索树
在树中的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值,没有键值相等的节点 红黑树
一种自平衡的二叉搜索树(BST)
性质1节点要么是红色,要么是黑色
性质2根节点是黑色
性质3叶子节点都是黑色的空节点
性质4红黑树中红色节点的子节点都是黑色
性质5从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
在添加或删除节点的时候如果不符合这些性质会发生旋转以达到所有的性质 散列表Hash Table
是根据键Key直接访问在内存存储位置值Value的数据结构,利用了数组支持按照下标进行随机访问数据的特性
散列函数计算得到的散列值必须是大于等于0的正整数因为hashValue需要作为数组的下标。
如果key1key2那么经过hash后得到的哈希值也必相同即hash(key1) hash(key2
如果key1 ! key2那么经过hash后得到的哈希值也必不相同即hash(key1) ! hash(key2)
散列冲突
不同的key计算得到的散列值都不同几乎是不可能的
链表法拉链
所有散列值相同的元素我们都放到相同槽位对应的链表中,链表法中的链表如果是红黑树可以防止DDos攻击 HashMap实现原理
底层使用hash表数据结构即数组和链表或红黑树
当我们往HashMap中put元素时利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
存储时如果出现hash值相同的key此时有两种情况 a. 如果key相同则覆盖原始值 b. 如果key不同出现冲突则将当前的key-value放入链表或红黑树中 获取时直接找到hash值对应的下标在进一步判断key是否相同从而找到对应值。
链表的长度大于8 且 数组长度大于64 转换为红黑树减少搜索时间
红黑树拆分成的树的结点数小于等于临界值6个则退化成链表
jdk1.7采用的是拉链法 链表和数组相结合
HashMap的put方法的具体流程
HashMap是懒惰加载在创建对象时并没有初始化数组
在无参的构造函数中设置了默认的加载因子是0.75 讲一讲HashMap的扩容机制 hashMap的寻址算法
计算对象的 hashCode()
再进行调用 hash() 方法进行二次哈希 hashcode值右移16位再异或运算让哈希分布更为均匀
最后 (capacity – 1) hash 得到索引
hashmap在1.7情况下的多线程死循环问题
尾插法
