商城网站建设哪家效益快,手机网站建设联系方式,《设计》在线观看,网站seo啥意思1.常见集合
Collection List#xff1a;有序可重复集合#xff0c;可直接根据元素的索引来访问 Vector-StackArrayListLinkedList Queue#xff1a;队列集合 Deque-LinkedList、ArrayDequePriorityQueue Set#xff1a;无序不可重复集合#xff0c;只能根据元素本身来访问…1.常见集合
Collection List有序可重复集合可直接根据元素的索引来访问 Vector-StackArrayListLinkedList Queue队列集合 Deque-LinkedList、ArrayDequePriorityQueue Set无序不可重复集合只能根据元素本身来访问 Hashset-LinkedHashSetSortedSet-TreeSetEnumSet Map存储key-value对的集合可根据元素的key来访问value IdentityHashmapWeakHashMapHashMap-LinkedHashMapHashTable-PropertiesSortedMap-TreeMapEnumMap
2.线程安全和线程不安全
线程安全Hashtable、ConcurrentHashMap、Vectorsynchronized、Stack线程不安全HashMap、ArrayList、LinkedList、HashSet、TreeSet、TreeMap
3.ArrayList与LinkedList
线程安全不安全底层数据结构 ArrayListObject数组LinkedList双向循环链表 插入删除是否受位置影响 ArrayList数组存储插入和删除元素的时间复杂度受元素位置影响LinkedList链表存储插入和删除元素时间复杂度不受位置影响 是否支持快速随机访问 ArrayList实现了RandomAccess接口能随机访问LinkedList不支持高效的随机元素访问 内存空间占用 ArrayList在list列表的结尾会预留一定的容量空间LinkedList每个元素都需要消耗比ArrayList更多的空间要存放直接后继和直接前驱和数据
4.ArrayList扩容机制
本质计算出新的扩容数组size后实例化并将原有数组内容复制到新数组去默认情况下新的容量会是原容量的1.5倍
5.Array和ArrayList
Array可以包含基本类型和对象类型ArrayList只能包含对象类型Array大小是固定的ArrayList的大小是动态变化的ArrayList提供了更多的方法和特性egaddAllremoveAlliterator等
6.HashMap
底层数据结构 1.7 数组链表链表主要解决哈希冲突1.8 数组链表红黑树链表过长会严重影响HashMap的性能红黑树搜索时间复杂度是Ologn链表是On。链表和红黑树的转换 当链表超过8且数据总量超过64才会转红黑树将链表转换成红黑树前会判断如果当前数组的长度小于64会选择先进行数组扩容而不是转换为红黑树以减少搜索时间。 解决hash冲突 开放定址法再散列法以p为基础再hash以此类推直到不冲突再哈希法提供多个hash函数直到不冲突链地址法HashMap采用的方法。哈希值相同的元素构成一个单链表建立公共溢出区将哈希表分为公共表和溢出表当溢出发生时将所有溢出数据统一放到溢出区 加载因子 Node[] table初始化长度为16负载因子默认0.75threshold是Hashmap所能容纳键值对的最大值thresholdlength*Load factor。在数组定义好长度之后负载因子越大所能容纳的键值对个数越多。0.75是对空间和时间效率的一个平衡选择一般不要修改除非在时间和空间比较特殊的情况下 如果内存空间很多而又对时间效率要求很高可以降低负载因子Load factor的值如果内存空间紧张而对时间效率要求不高可以增加负载因子loadFactory的值这个值可以大于1 key的存储索引怎么计算的 根据key的值计算出hashcode的值根据hashcode计算出hash的值hashlength-1计算得到存储位置 put流程 根据key计算出hash值找到该元素再数组中存储的下标如果数组是空的调用resize进行初始化如果没有哈希冲突直接放在对应的数组下标里如果冲突且key已经存在覆盖掉value如果冲突发现该节点是红黑树就将这个节点挂在树上如果冲突后是链表判断该链表是否大于8 如果大于8并且数组容量小于64就扩容。如果节点大于8并且数组容量大于64结构转为红黑树否则链表插入键值对若key存在就覆盖掉value 扩容 容量超过负载因子所定义的容量之后就会扩容。将HashMap的大小扩大为原来数组的两倍并将原来的对象放到新的数组中。1.8两处优化 resize之后元素的位置在原来的位置或者原来位置oldCap。如果bit是0索引没变如果是1则为原索引oldcap1.7中rehash的时候旧链表迁移新链表的时候如果在新表的数组索引位置相同则链表元素会倒置头插法1.8不会倒置使用尾插法。 hashMap的key一般用IntegerString这种不可变类当keyString最常用 因为字符串是不可变的所以创建的时候hashcode就被缓存了不需要重新计算获取对象的时候要用到equals和hashcode键对象正确的重写这两个方法是非常重要的。 为什么是线程不安全的 多线程下扩容死循环1.7头插法导致的1.8不会出现环形链表的问题多线程的put可能导致元素的丢失。如果计算出的索引位置相同会造成前一个key被后一个key覆盖从而导致元素丢失。put 和 get 并发时可能导致get为null。线程1执行put因为元素个数超出threshold导致rehash线程2此时执行get有可能导致这个问题。
7.ConcurrentHashMap
实现原理 1.7 由segment数组结构和HashEntry数组结构组成把哈希桶切分成小数组每个小数组有n个HashEntry组成。 segment继承了ReentrantLock所以segment是一种可重入锁扮演锁的角色HashEntry用于存储键值对数据 1.8 选择了与hashmap相同的数组链表红黑树结构。在锁的实现上抛弃了原有的Segment分段锁采用cassynchronized实现更加低粒度的锁。将锁级别控制在了更细粒度的哈希桶元素级别提高并发度 put逻辑 1.7 尝试获取锁获取失败利用自旋获取锁如果自旋重试次数超过64次则改为阻塞获取锁获取到锁后 将当前segment中的table通过key的hashcode定位到HashEntry遍历该HashEntry如果不为空则判断传入的key和当前遍历的key是否相等相等则覆盖旧的value不为空则需要新建一个HashEntry并加入到Segment中同时会先判断是否需要扩容释放segment的锁 1.8 根据key计算出hash的值判断是否需要进行初始化定位到Node拿到首节点f判断首节点f 如果为null则通过cas的方式尝试添加如果为f.hashMOVED-1说明其他线程在扩容参与一起扩容如果都不满足synchronized锁住f节点判断是链表还是红黑树遍历插入 当在链表长度达到8的时候数组扩容或者将链表转换为红黑树 get方法不需要加锁 Node的元素val和指针next是用volatile修饰的在多线程环境下线程A修改节点的val或者新增节点的时候是对线程B可见的。与volatile修饰的哈希桶没有关系哈希桶主要是保证在数组扩容的时候保证可见性 不支持key或者value为null value不为null无法判断是映射的value为null还是没找到对应的key而为null。 并发度 1.7 默认16可以在构造函数中设置如果设置了并发度ConcurrentHashMap会使用大于等于该值的最小的2的幂指数作为实际并发度即如果设置的是17则实际并发度为32 迭代器是强一致性还是弱一致性 HashMap是强一致性ConcurrentHashMap是弱一致性迭代器创建后会按照哈希表结构遍历每个元素在遍历过程中内部元素可能发生变化如果变化发生在已遍历过的部分迭代器就不会反映出来而如果变化发生在未遍历过的部分迭代器会 发现并反映出来即弱一致性。
8.Hashtable
使用Synchronized来实现线程安全多线程访问的时候只有一个线程能访问或操作对象。
9.多线程下安全的操作map还有其他方法么
Collections.synchronizedMap对方法进行加同步锁。如果传入的是HashMap对象也是对HashMap做了一层包装里面使用对象锁来保证多线程场景下线程安全本质也是全表锁。
10.Collection框架中实现比较
内部比较器实体类实现Comparable接口并实现compareToT t方法外部比较器实现Comparator接口的compareT t1T t2
11.Iterator 和 ListIterator
Iterator遍历可以遍历所有集合egMapListSet但只能再向前方向上遍历集合中的元素ListIterator只能遍历List实现的对象但可以向前和向后遍历集合中的元素 区别 添加元素Iterator无法向集合中添加元素ListIterator可以向集合中添加元素修改元素Iterator无法修改元素ListIterator可以使用set修改集合中的元素索引Iterator无法获取集合中元素的索引ListIterator可以获取结合中的索引
12.快速失败和安全失败
快速失败fail-fast 在用迭代器遍历一个集合对象时 如果遍历过程中集合对象的内容进行了修改增删改则会抛出ConcurrentModificationException原理迭代器在遍历时直接访问集合中的内容并且在遍历过程中使用一个modCount变量集合在被遍历期间如果内容发生变化就会改变modCount的值每当迭代器使用hashNext/next遍历下一个元素之前都会检测modCount变量是否为expectedmodCount值是的话就返回遍历否则抛出异常终止遍历。注这里异常的抛出条件是检测到modCount ! expectedmodCount这个条件如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值则异常不会抛出因此不能依赖于这个异常是否抛出而进行并发操作的编程这个异常只建议用于检测并发修改的bug场景java.util包下的集合类都是快速失败的不能在多线程下发生并发修改迭代过程中被修改比如hashmaparrayList这些集合类 安全失败fail-safe 采用安全失败机制的集合容器在遍历时不是直接在集合内容上访问的而是先复制原有集合内容在拷贝的集合上进行遍历原理由于迭代时是对原集合的拷贝进行遍历所以在遍历过程中对原集合所作的修改并不能被迭代器检测到所以不会触发ConcurrentModification Exception缺点基于拷贝内容的优点避免了ConcurrentModificationException但同样滴迭代器并不能访问到修改后的内容即迭代器遍历的是开始遍历那一刻拿到的集合拷贝在遍历期间原集合发生的修改迭代器是不知道的场景java.util.concurrent包下的容器都是安全失败的可以在多线程下并发使用并发修改比如ConcurrentHashMap
