南宁建筑网站,wordpress菜单怎么添加次级菜单,aspx高性能网站建设,设计服务网站Java集合框架体系 重点#xff1a;单列集合——ArrayList、LinkedList#xff1b;双列集合——HashMap、ConcurrentHashMap。
List相关
数组#xff08;Array#xff09; 是一种用连续的内存空间存储相同数据类型数据的线性数据结构。 数组获取其他元素#xff1a; 为什…Java集合框架体系 重点单列集合——ArrayList、LinkedList双列集合——HashMap、ConcurrentHashMap。
List相关
数组Array 是一种用连续的内存空间存储相同数据类型数据的线性数据结构。 数组获取其他元素 为什么数组索引从0开始呢假如从1开始不行吗
在根据数组索引获取元素的时候会用索引和寻址公式来计算内存所对应的元素数据寻址公式是数组的首地址索引乘以存储数据的类型大小在这里插入图片描述 如果数组的索引从1开始寻址公式中就需要增加一次减法操作对于CPU来说就多了一次指令性能不高。 查找的时间复杂度随机(通过下标)查询的时间复杂度是O(1)查找元素未知下标的时间复杂度是O(n)查找元素未知下标但排序通过二分查找的时间复杂度是O(logn)
插入和删除时间复杂度
插入和删除的时候为了保证数组的内存连续性需要挪动数组元素平均时间复杂度为O(n)
ArrayList源码分析
成员变量 /*** 默认初始的容量(CAPACITY)*/private static final int DEFAULT_CAPACITY 10;/*** 用于空实例的共享空数组实例*/private static final Object[] EMPTY_ELEMENTDATA {};/*** 用于默认大小的空实例的共享空数组实例。* 我们将其与 EMPTY_ELEMENTDATA 区分开来以了解添加第一个元素时要膨胀多少*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};/*** 存储 ArrayList 元素的数组缓冲区。 ArrayList 的容量就是这个数组缓冲区的长度。* 当添加第一个元素时任何具有 elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList* 都将扩展为 DEFAULT_CAPACITY* 当前对象不参与序列化*/transient Object[] elementData; // non-private to simplify nested class access/*** ArrayList 的大小它包含的元素数量** serial*/private int size;构造方法 构造方法1——带初始化容量的构造函数 public ArrayList(int initialCapacity) {if (initialCapacity 0) {this.elementData new Object[initialCapacity];} else if (initialCapacity 0) {this.elementData EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}} 构造方法2——无参构造函数默认创建空集合 public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}构造方法3——将collection对象转换成数组然后将数组的地址的赋给elementData public ArrayList(Collection? extends E c) {Object[] a c.toArray();if ((size a.length) ! 0) {if (c.getClass() ArrayList.class) {elementData a;} else {elementData Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData EMPTY_ELEMENTDATA;}}关键方法 第一次添加数据调用add方法添加数据流程 第十次添加数据 第十一次添加数据
总结
ArrayList的底层使用动态的数组实现的它的初始容量为0当第一次添加数据的时会初始化容量为10在扩容后容量是原来容量的1.5倍每次扩容都需要拷贝数据添加逻辑 确保数组已使用长度size加1之后足够存下下一个数据计算数组的容量如果当前数组已使用长度1后的大于当前的数组长度则调用grow方法扩容原来的1.5倍确保新增的数据有地方存储之后则将新元素添加到位于size的位置上。返回添加成功布尔值。
问题 ArrayList listnew ArrayList(10)中的list扩容几次 回答 该语句只是声明和实例了一个 ArrayList指定了容量为 10未扩容。
Array与List相互转换
数组转List 使用JDK中java.util.Arrays工具类的asList方法List转数组使用List的toArray方法。无参toArray方法返回 Object数组传入初始化长度的数组对象返回该对象数组。 //数组转Listpublic static void testArray2List() {String[] strs {aaa, bbb, ccc};ListString list Arrays.asList(strs);for (String s : list) {System.out.println(s);}}//List转数组public static void testList2Array() {ListString list new ArrayListString();list.add(aaa);list.add(bbb);list.add(ccc);String[] array list.toArray(new String[list.size()]);for (String s : array) {System.out.println(s);}}注意 Arrays.asList转换list之后如果修改了数组的内容list会受影响因为它的底层使用的Arrays类中的一个内部类ArrayList来构造的集合在这个集合的构造器中把我们传入的这个集合进行了包装而已最终指向的都是同一个内存地址。源码如下图所示 list用了toArray转数组后如果修改了list内容数组不会影响当调用了toArray以后在底层是它是进行了数组的拷贝跟原来的元素就没啥关系了所以即使list修改了以后数组也不受影响。源码如下图所示 测试代码 //数组转Listpublic static void testArray2List() {String[] strs {aaa, bbb, ccc};ListString list Arrays.asList(strs);for (String s : list) {System.out.println(s);}strs[1] ddd;System.out.println();for (String s : list) {System.out.println(s);}}//List转数组public static void testList2Array() {ListString list new ArrayListString();list.add(aaa);list.add(bbb);list.add(ccc);String[] array list.toArray(new String[list.size()]);for (String s : array) {System.out.println(s);}list.add(ddd);System.out.println();for (String s : array) {System.out.println(s);}}
ArrayList和LinkedList的区别 底层数据结构 ArrayList 使用动态数组实现它内部维护一个 Object 数组在添加或删除元素时会涉及到数组的扩容和拷贝操作。LinkedList 使用双向链表实现它的每个元素都包含了对前后元素的引用添加或删除元素时只需要修改相邻节点的引用不涉及数组的扩容和拷贝操作。 访问效率 ArrayList 支持随机访问通过索引访问因为它是基于数组实现的可以通过索引直接定位到元素。因此对于随机访问的操作效率比较高时间复杂度为 O(1)。LinkedList 不支持随机访问因为它是基于链表实现的需要从头节点或尾节点开始顺序查找时间复杂度为 O(n)其中 n 为链表长度。但在插入和删除操作上LinkedList 由于不涉及数组的扩容和拷贝且只需修改相邻节点的引用因此插入和删除操作的效率较高时间复杂度为 O(1)。 新增和删除 ArrayList尾部插入和删除时间复杂度是O(1)其他部分增删需要挪动数组时间复杂度是O(n)。LinkedList头尾节点增删时间复杂度是O(1)其他都需要遍历链表时间复杂度是O(n)。 空间复杂度 ArrayList 在添加元素时可能需要进行数组的扩容而扩容操作需要重新分配内存空间并将原数组的元素拷贝到新数组中因此可能会导致额外的内存消耗。LinkedList 每个元素都需要额外的空间来存储前后节点的引用因此相比 ArrayList 需要更多的内存空间。 线程安全 ArrayList和LinkedList都不是线程安全的。如果需要保证线程安全有两种方案 在方法内使用局部变量则是线程安全的使用线程安全的ArrayList和LinkedList如 ListObject syncArrayList Collections.synchronizedList(new ArrayList());
ListObject syncLinkedList Collections.synchronizedList(new LinkedList());HashMap相关
二叉树每个节点最多有两个“叉”也就是两个子节点分别是左子节点和右子节点。不过二叉树并不要求每个节点都有两个子节点有的节点只有左子节点有的节点只有右子节点。 二叉树每个节点的左子树和右子树也分别满足二叉树的定义。 如图所示
Java中有两个方式实现二叉树数组存储链式存储。 基于链式存储的树的节点可定义如下 public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left left;this.right right;}}在二叉树中比较常见的二叉树有
满二叉树完全二叉树二叉搜索树红黑树
二叉搜索树(Binary Search Tree,BST) 又名二叉查找树有序二叉树或者排序二叉树是二叉树中比较常用的一种类型。 二叉查找树要求在树中的任意一个节点其左子树中的每个节点的值都要小于这个节点的值而右子树节点的值都大于这个节点的值。 二叉树的插入查找删除的时间复杂度O(logn)最坏的情况下二叉树会退化成链表此时的查找时间复杂度为O(n)如图 红黑树Red Black Tree也是一种自平衡的二叉搜索树(BST)之前叫做平衡二叉B树Symmetric Binary B-Tree它在每个节点上增加了一个额外的表示节点颜色的属性可以是红色或黑色如下图所示。红黑树通过一系列的规则确保了树的平衡从而保证了在最坏情况下的基本操作如查找、插入和删除具有较低的时间复杂度。
红黑树具有以下特性
节点颜色每个节点都是红色或黑色。根节点根节点是黑色的。叶子节点叶子节点NIL 节点或空节点是黑色的。红色节点红色节点的两个子节点都是黑色的。路径规则从任一节点到其每个叶子节点的路径上黑色节点的数量相同。
当插入和删除操作可能会破坏红黑树的特性因此需要进行修正以恢复树的平衡。
红黑树的复杂度
查找 红黑树也是一棵BST二叉搜索树树查找操作的时间复杂度为O(log n)添加 添加先要从根节点开始找到元素添加的位置时间复杂度O(log n) 添加完成后涉及到复杂度为O(1)的旋转调整操作 故整体复杂度为O(log n)删除 首先从根节点开始找到被删除元素的位置时间复杂度O(log n) 删除完成后涉及到复杂度为O(1)的旋转调整操作 故整体复杂度为O(log n)
HashMap
散列表 散列表(Hash Table)又名哈希表/Hash表是根据键Key直接访问在内存存储位置值Value的数据结构它是由数组演化而来的利用了数组支持按照下标进行随机访问数据的特性。 如图 将键(key)映射为数组下标的函数叫做散列函数。 可以表示为hashValue hash(key)。
散列函数的基本要求
散列函数计算得到的散列值必须是大于等于0的正整数因为hashValue需要作为数组的下标。如果key1key2那么经过hash后得到的哈希值也必相同即hash(key1) hash(key2如果key1 ! key2那么经过hash后得到的哈希值也必不相同即hash(key1) ! hash(key2)——但不太好实现
实际的情况下想找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的即便像著名的MD5,SHA等哈希算法也无法避免这一情况这就是散列冲突(或者哈希冲突哈希碰撞就是指多个key映射到同一个数组下标位置) 。
避免Hash冲突——拉链法在散列表中数组的每个下标位置我们可以称之为桶bucket或者槽slot每个桶(槽)会对应一条链表 所有散列值相同的元素我们都放到相同槽位对应的链表中。如图所示 基于拉链法分析散列表的时间复杂度
插入操作 通过散列函数计算出对应的散列槽位将其插入到对应链表中即可插入的时间复杂度是 O(1) 查找、删除操作 当查找、删除一个元素时同样通过散列函数计算出对应的槽然后遍历链表查找或者删除 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)散列表可能会退化为链表,查询的时间复杂度就从 O(1) 退化为 O(n)将链表法中的链表改造为其他高效的动态数据结构比如红黑树查询的时间复杂度是 O(logn)
HashMap实现原理
HashMap的数据结构 底层使用hash表数据结构即数组和链表或红黑树 。
当我们往HashMap中put元素时利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时如果出现hash值相同的key此时有两种情况。 a. 如果key相同则覆盖原始值 b. 如果key不同出现冲突则将当前的key-value放入链表或红黑树中获取时直接找到hash值对应的下标在进一步判断key是否相同从而找到对应值。 HashMap的jdk1.7和jdk1.8有什么区别
JDK1.8之前采用的是拉链法。拉链法将链表和数组相结合。也就是说创建一个链表数组数组中每一格就是一个链表。若遇到哈希冲突则将冲突的值加到链表中即可。JDK1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为8 时并且数组长度达到64时将链表转化为红黑树以减少搜索时间。扩容 resize( ) 时红黑树拆分成的树的结点数小于等于临界值6个则退化成链表。
HashMap的put方法的具体流程
HashMap常见属性
static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16
static final float DEFAULT_LOAD_FACTOR 0.75f;
transient HashMap.NodeK,V[] table;
transient int size;DEFAULT_INITIAL_CAPACITY 默认的初始容量
DEFAULT_LOAD_FACTOR 默认的加载因子扩容阈值 数组容量 * 加载因子其中 table变量的所属类 static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue value;value newValue;return oldValue;}public final boolean equals(Object o) {if (o this)return true;return o instanceof Map.Entry?, ? e Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue());}}HashMap的无参构造方法
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted}说明
HashMap是懒惰加载在创建对象时并没有初始化数组在无参的构造函数中设置了默认的加载因子是0.75
添加数据的流程图
判断键值对数组table是否为空或为null否则执行resize()进行扩容初始化根据键值key计算hash值得到数组索引判断table[i]null条件成立直接新建节点添加如果table[i]null ,不成立 判断table[i]的首个元素是否和key一样如果相同直接覆盖value判断table[i] 是否为treeNode即table[i] 是否是红黑树如果是红黑树则直接在树中插入键值对遍历table[i]链表的尾部插入数据然后判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操 作遍历过程中若发现key已经存在直接覆盖value 插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold数组长度*0.75如果超过进行扩容。
put方法流程
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//判断数组是否未初始化if ((tab table) null || (n tab.length) 0)//如果未初始化调用resize方法 进行初始化n (tab resize()).length;//通过 运算求出该数据key的数组下标并判断该下标位置是否有数据if ((p tab[i (n - 1) hash]) null)//如果没有直接将数据放在该下标位置tab[i] newNode(hash, key, value, null);//该数组下标有数据的情况else {NodeK,V e; K k;//判断该位置数据的key和新来的数据是否一样if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))//如果一样证明为修改操作该节点的数据赋值给e,后边会用到e p;//判断是不是红黑树else if (p instanceof TreeNode)//如果是红黑树的话进行红黑树的操作e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);//新数据和当前数组既不相同也不是红黑树节点证明是链表else {//遍历链表for (int binCount 0; ; binCount) {//判断next节点如果为空的话证明遍历到链表尾部了if ((e p.next) null) {//把新值放入链表尾部p.next newNode(hash, key, value, null);//因为新插入了一条数据所以判断链表长度是不是大于等于8if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是进行转换红黑树操作treeifyBin(tab, hash);break;}//判断链表当中有数据相同的值如果一样证明为修改操作if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;//把下一个节点赋值为当前节点p e;}}//判断e是否为空e值为修改操作存放原数据的变量if (e ! null) { // existing mapping for key//不为空的话证明是修改操作取出老值V oldValue e.value;//一定会执行 onlyIfAbsent传进来的是falseif (!onlyIfAbsent || oldValue null)//将新值赋值当前节点e.value value;afterNodeAccess(e);//返回老值return oldValue;}}//计数器计算当前节点的修改次数modCount;//当前数组中的数据数量如果大于扩容阈值if (size threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//添加操作时 返回空值return null;
}HashMap的扩容
流程图
在添加元素或初始化的时候需要调用resize方法进行扩容第一次添加数据初始化数组长度为16以后每次每次扩容都是达到了扩容阈值数组长度 * 0.75每次扩容的时候都是扩容之前容量的2倍扩容之后会新创建一个数组需要把老数组中的数据挪动到新的数组中 没有hash冲突的节点则直接使用 e.hash (newCap - 1) 计算新数组的索引位置如果是红黑树走红黑树的添加如果是链表则需要遍历链表可能需要拆分链表判断(e.hash oldCap)是否为0该元 素的位置要么停留在原始位置要么移动到原始位置增加的数组大小这个位置上
扩容
//扩容、初始化数组
final NodeK,V[] resize() {NodeK,V[] oldTab table;//如果当前数组为null的时候把oldCap老数组容量设置为0int oldCap (oldTab null) ? 0 : oldTab.length;//老的扩容阈值int oldThr threshold;int newCap, newThr 0;//判断数组容量是否大于0大于0说明数组已经初始化if (oldCap 0) {//判断当前数组长度是否大于最大数组长度if (oldCap MAXIMUM_CAPACITY) {//如果是将扩容阈值直接设置为int类型的最大数值并直接返回threshold Integer.MAX_VALUE;return oldTab;}//如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap*2//运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold 等价于oldThr*2}//如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;//数组未初始化的情况将阈值和扩容因子都设置为默认值else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//初始化容量小于16的时候扩容阈值是没有赋值的if (newThr 0) {//创建阈值float ft (float)newCap * loadFactor;//判断新容量和新阈值是否大于最大容量newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//计算出来的阈值赋值threshold newThr;SuppressWarnings({rawtypes,unchecked})//根据上边计算得出的容量 创建新的数组 NodeK,V[] newTab (NodeK,V[])new Node[newCap];//赋值table newTab;//扩容操作判断不为空证明不是初始化数组if (oldTab ! null) {//遍历数组for (int j 0; j oldCap; j) {NodeK,V e;//判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作if ((e oldTab[j]) ! null) {//将数组位置置空oldTab[j] null;//判断是否有下个节点if (e.next null)//如果没有就重新计算在新数组中的下标并放进去newTab[e.hash (newCap - 1)] e;//有下个节点的情况并且判断是否已经树化else if (e instanceof TreeNode)//进行红黑树的操作((TreeNodeK,V)e).split(this, newTab, j, oldCap);//有下个节点的情况并且没有树化链表形式else {//比如老数组容量是16那下标就为0-15//扩容操作*2容量就变为32下标为0-31//低位0-15高位16-31//定义了四个变量// 低位头 低位尾NodeK,V loHead null, loTail null;// 高位头 高位尾NodeK,V hiHead null, hiTail null;//下个节点NodeK,V next;//循环遍历do {//取出next节点next e.next;//通过 与操作 计算得出结果为0if ((e.hash oldCap) 0) {//如果低位尾为null证明当前数组位置为空没有任何数据if (loTail null)//将e值放入低位头loHead e;//低位尾不为null证明已经有数据了else//将数据放入next节点loTail.next e;//记录低位尾数据loTail e;}//通过 与操作 计算得出结果不为0else {//如果高位尾为null证明当前数组位置为空没有任何数据if (hiTail null)//将e值放入高位头hiHead e;//高位尾不为null证明已经有数据了else//将数据放入next节点hiTail.next e;//记录高位尾数据hiTail e;}} //如果e不为空证明没有到链表尾部继续执行循环while ((e next) ! null);//低位尾如果记录的有数据是链表if (loTail ! null) {//将下一个元素置空loTail.next null;//将低位头放入新数组的原下标位置newTab[j] loHead;}//高位尾如果记录的有数据是链表if (hiTail ! null) {//将下一个元素置空hiTail.next null;//将高位头放入新数组的(原下标原数组容量)位置newTab[j oldCap] hiHead;}}}}}//返回新的数组对象return newTab;}HashMap的get 方法
public V get(Object key) {NodeK,V e;//hash(key)获取key的hash值//调用getNode方法见下面方法return (e getNode(hash(key), key)) null ? null : e.value;
}final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;//找到key对应的桶下标赋值给first节点if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {//判断hash值和key是否相等如果是则直接返回桶中只有一个数据大部分的情况if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;if ((e first.next) ! null) {//该节点是红黑树则需要通过红黑树查找数据if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);//链表的情况则需要遍历链表查找数据do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;
}HashMap的寻址算法
在HashMap中计算hash值时用到的关键方法
计算hash值时用到的两个技巧
将key的hashCode右移16位后再进行异或运算——(h key.hashCode()) ^ (h 16)这称为扰动算法使hash值更加均匀从而减少hash冲突。(n-1)hash : 得到数组中的索引代替取模性能更好运算结果与取模运算一样。数组长度必须是2的n次幂
HashMap的数组长度一定是2的次幂
计算索引时效率更高如果是 2 的 n 次幂可以使用位与运算代替取模扩容时重新计算索引效率更高 hash oldCap 0 的元素留在原来位置 否则新位置 旧位置 oldCap
