java集合相关知识

文章目录1. Collection1概述2) 常用方法3) 单列集合和双列集合的比较2. 迭代器1 出现的原因2概述3具体操作4) 底层原理5 增强for循环6 注意点7遍历过程中修改集合长度3. List1 概述2 常用的实现类3 list接口中常用的方法4 ArrayList5 LinkedList6 Vector4. Set1) 概述2 常用的实现类3HashSet4LinkedHashSet5TreeSet5. Map1) 概述2 常见的实现类3 Map集合中常见的方法3 Map集合的遍历4 HashMap5 LinkedHashMap6 HashTable7 TreeMap8 CurrentHashMap9 hashTable和hashMap的区别10CAS锁6. 容器线程安全性对比1. Collection1概述1. 集合是java中提供的一种容器可以用来存储多个数据。 2. Collection是所有单列集合的顶层接口。其他的单列集合都直接或间接的实现了Collection接口。 3. 集合的底层是一个可变的Object数组。当数组原来的长度满了以后集合会进行扩容(一般是1.5倍)创建一个新的数组 将原来数组中的数据存放进去然后把原来的数组删掉改用新的扩容后的数组。 4. 集合和数组的具体区别为 1数组的长度是固定的集合的长度是可变的。 2数组可以存放任意类型的数据集合只能存放引用类型的数据。【集合虽然不能存放基本数据类型但是可以存放基本数据类型对应的包装类】Collection接口的实现2) 常用方法1. public Boolean add(E e) ; 向集合中添加元素 2. public Boolean remove(E e); 删除集合中指定的元素如果有多个只会删除出现的第一个。 3. public Boolean contains(E e); 判断当前集合中是否包含某个指定对象 4. public Boolean isEmpty(); 判断当前集合是否为空 5. public int size(); 返回集合中元素的个数 6. public void clear(); 清除集合中的所有元素 7. public Object[ ] toArray(); 把集合中的元素存储到数组中(集合转数组)3) 单列集合和双列集合的比较单列集合中的每个元素都是单独的。 双列集合中的每个元素都是键值对(成对存在)。单列集合和双列集合的比较2. 迭代器1 出现的原因并不是所有的集合都有索引比如底层是链表结构的集合。 针对没有索引的元素无法通过索引直接查询到对应的值只能一个一个遍历去查找。 有一种通用的便利集合的方法叫做 迭代器遍历。2概述1. 迭代器是一个便利集合的工具。 2. 迭代器内部有一个光标这个光标最开始指向集合的最开头每次遍历都会向后移动一个位置。 3. 迭代器的获取 调用Collection中的 iterator() 方法就可以获取到集合中的迭代器。 IteratorE iterator() 4. 其他方法 boolean hasNext() 判断是否还有元素可以获取 E next() 获取当前迭代器光标位置的元素然后让光标向后移动一个位置。3具体操作1. 遍历具体操作 a. 调用集合的 iterator() 方法获取集合对应的迭代器。 b. 通过迭代器调用 hasNext() 方法判断是否还有元素可以获取。 c. 如果还有元素可以获取就调用 next() 方法进行获取当前光标位置的元素并将光标向后移动一个位置。 eg: IteratorString iterator list.iterator(); while(iterator.hasNext()){ String value iterator.next(); }4) 底层原理5 增强for循环1. 格式 for(数据类型 变量名 容器){ //代码块 } 2. 注意点 a. 当使用增强for循环遍历数组时底层是普通for循环(使用索引)。 b. 当使用增强for循环遍历实现了Iterable接口的集合(如list、set)时底层使用的是迭代器循环。 3. 优点省略了对索引的操作代码更简洁。 4. 缺点 无法获取索引如果要对索引进行操作还需要使用普通for循环。6 注意点1. 如果在迭代器中使用集合的方法对集合的长度进行改变操作那么就会造成并发操作异常 (java.util.ConcurrentModificationException)。 2. 针对集合的增强for循环因为底层也是迭代器所以如果对集合的长度进行操作add(),remove()等那么也会造成并发操作异常直接报错。7遍历过程中修改集合长度1. 删除元素 1. 普通for循环可以删除但是需要手动修改索引如果是从大到小遍历不需要修改索引如果是从小到大遍历删除后需要把索引减去1。 2. 增强for循环底层是迭代器不可以删除直接删除是调用的集合的remove()方法会抛出异常ConcurrentModificationException 3. 迭代器循环可以删除调用的是迭代器自己的remove()方法但是需要先调用next()方法。保证有元素。 2. 增加元素 1. 普通for循环不可以增加。 2. 增强for循环不可以增加。 3. 迭代器普通迭代器(Iterator) 不可以增加list集合迭代器(ListIterator)可以增加。图示3. List1 概述list接口是collection下面的一个子接口主要有这些特点 1. 有序怎么存进去的就怎么取出来存进去和取出来的顺序一样。 2. 有索引可以通过索引来获取元素。 3. 可以存放重复的元素。2 常用的实现类list 是一个接口使用的时候要使用它的实现类list 常用的实现类有 1. ArrayList 2. LinkedList 3. Vector3 list接口中常用的方法1. public void add(int index, E element) // 将指定的元素添加到集合指定的索引位置上 2. public E get(int index ) //获取指定索引位置上的元素 3. public E remove(int index ); //移除指定索引位置上的元素返回的是被移除的元素 4. public E set(int index, E element); //用指定元素替换集合中指定索引位置上的元素返回的是被替换掉的元素。4 ArrayList1. 数据结构 ArrayList内部是使用的一个可变的Object数组来存储数据的。 数组在内存中是连续存储的。 一般我们说的数组的地址是第一个元素的位置。 2. 特点 因为底层是数组所以查询块增删慢。 线程不安全但是性能比较高。 3. 方法 1 ArrayListString list new ArrayList(); //构造方法 2 public boolean add(E e) //将指定的元素添加到此集合的尾部 3 public E remove(int index) //移除此集合中指定索引位置上的元素返回被删除的元素 4 public E set(int index, E e) //修改索引位置为index的元素的值为 e;返回修改前index位置上的元素被修改的元素 5 public E get(int index ) //查询索引位置为index的元素的值 6 public int size() //获取元素总数量 7public Boolean contains (Object o) //查询集合中是否含有元素o,返回布尔值。 4. 注意点 1 ArrayList对象不能存储基本数据类型只能存储引用数据类型。 2 ArrayList虽然不能存储基本数据类型但是可以存储基本数据类型对应的包装类型所以如果需要存储基本数据类型 可以设置数据类型为基本数据类型的包装类赋值的时候直接赋值基本数据类型(自动拆装箱)。 5. 使用场景 当以查询和尾部操作为主或内存和性能要求较高时使用。 6. 扩容原则 1使用无参构造时初始是一个空数组。 2第一次添加元素的时候默认是10如果元素数量大于10那么就是元素数量。 3再次扩容时会变为当前数量的1.5倍如果1.5倍不够那么就会变成所需要的最小元素数量。5 LinkedList1. 数据结构 a. LinkedList 内部是一个双向链表。 b. 链表在内存中的存储位置不是连续的它是由很多个节点组成的 每个节点至少包括两个部分一部分用来存储数据另一部分是指向下个节点的地址值。 c. 双向链表结构 节点中不仅有指向下一个节点的地址值还有指向上一个节点的地址值所以双向链表是有序的。查询的时候效率会稍微高一些但是还是比list慢好多。 2. 特点 查询慢增删快 3. 特有方法 1 public void addFirst(E e) //将指定元素插入到列表的开头 2 public void addLast(E e) //将指定元素插入到列表的末尾 3 public E getFirst() //获取集合中首个位置的元素 4 public E getLast(); //获取集合中最后位置的元素 5 E removeFirst() //删除集合中第一个元素并返回被删除的元素 6 E removeLast() //删除集合中最后一个元素并返回被删除的元素 7 void push(E e) //压入向集合的开头添加元素调用的方法就是addFirst(E e ) 8 E pop() //弹出删除集合中第一个元素并返回调用的方法就是removeFirst() 4. 使用场景 当需要频繁修改列表结构尤其是头/中部操作或实现特定数据结构如队列时。6 Vector1. 底层结构 底层是一个动态数组属于线程安全版的ArrayList. 2. 特点 1 线程安全但是效率低。 2 扩容策略不同默认为原容量的2倍ArrayList 是原容量的1.5倍。4. Set1) 概述1. set接口是Collection接口下面的另一个子接口。 2. set接口的主要特点是 a. 无序怎么存进去的不一定按照顺序取出来 b. 无索引 c. 不可重复2 常用的实现类1. HashSet 2. LinkedHashSet 3. TreeSet3HashSet1. 介绍 HashSet是Set接口的实现类这个类满足set接口的所有特点无序无索引不可重复。 2. 遍历 因为set接口是无序的所有HashSet也是无序的因此HashSet不能通过索引进行遍历只能通过迭代器或者增强for循环 进行遍历。 3. 对象的哈希值 1 哈希值是一个int数字可以把哈希值看作对象的一个标识但并不是唯一标识哈希值可以重复。 2 在Object对象中有一个方法可获取到对象的哈希值这个方法是 HashCode()方法。 3 Object对象中的HashCode()方法对应的哈希值计算方式是根据地址值计算的所以哪怕两个对象的属性值一样只要地址值不一样他们的哈希值就不一样。所以除非是同一个对象不然他们的哈希值是不一样的。 4 如果不想使用Object对象中的哈希值计算方法那么可以在子类中重写HashCode()方法。没有重写前是根据地址值计算哈希值重写后自己可以定义比如只要对象的属性值完全相同那么他们的哈希值就一样。 4. 哈希表 1 哈希表将对象根据哈希值分类后的结果是一个数组结构数组中的每个元素都是一个链表。链表中的内容都是归并后的内容。 2 在jdk1.8及以后如果链表的长度超过了8那么这个链表会自动变成红黑树结构。 3 桶 数组中的每一个元素都是一个桶。因为数组中的每个元素都是一个链表所以对应的这个链表都是一个桶。 4 哈希冲突出现在同一个桶内的对象就是哈希冲突哪怕这些对象的哈希值不一样也是。 5 加载因子 是一个百分比加载因子 哈希表中当前元素总数量 / 哈希表中桶的总数量计算的是每个桶平均承载的元素数量默认是0.75。当桶内元素的平均数量超过加载因子时就会进行再哈希。 6 再哈希对哈希表进行扩容让分类更广泛。 5. HashSet判断唯一性的原理 1) 首先会比较两个对象的哈希值是否一样如果不一样那么一定不同如果一样可能相同。 2) 如果两个对象的哈希值一样那么会再调用对象的equals()方法进行比较如果两个对象的equals()方法比较结果也一样那么就会认为这两个对象一样(不会存入)如果调用equals()方法比较之后结果不同那么就认为这两个对象不一样可以存入。 6. HashSet存放自定义元素 1 实际使用中我们判断对象是否相同一般不是比较地址值而是只要对象的属性值相同就认为相同所以一般都会重写equals()方法和hashCode()方法。 2 因为如果不重写默认使用的是Object对象中的equals()方法和hashCode()方法,比较的是地址值哪怕两个对象的属性值一样他们的哈希值也不一样。哈希表结构4LinkedHashSet1. 概述 1 LinkedHashSet是Set接口的实现类具体特点为有序无索引不可重复。 2 LinkedHashSet有序的原因底层是由双向链表和哈希表组合成的一个数据存储结构。 双向链表保证了数据的有序性。5TreeSet1. 概述 1底层实现是红黑树基于TreeMap。 2. HashSet 和 TreeSet 的区别5. Map1) 概述1. Map集合是一个双列集合里面的每一个元素都是由键值对组成的。 2. Map集合的特点 键不可以重复值可以重复通过每个键都就可以找到唯一对应的值。2 常见的实现类1. HashMap 2. LinkedHashMap 3. HashTable 4. TreeMap3 Map集合中常见的方法1. V put(K key, V value) //向Map集合中添加键值对 注意 1 如果添加的时候key之前已经存在那么会使用新的value值覆盖之前的value值。 2) 调用put()方法如果没有产生覆盖效果返回的是null如果产生了覆盖效果返回的是被覆盖掉的值。 2. V get(Object key) //根据键获取对应的值如果键不存在那么得到的值是null 3. V remove(Object key) //根据键删除整个键值对返回的是被删除掉的值3 Map集合的遍历1. 因为Map集合内部是键值对的形式所以不能直接使用迭代器或者增强for对Map进行遍历。 2. 需要先获取到key的集合或者entry的集合再进行遍历。 3. 遍历Map集合的方法有 1调用 Map.keySet()方法获取所有的key放到set集合中再对set集合进行遍历。 2调用 Map.entrySet()方法获取到所有的entry对象放到一个set中再对set进行遍历。4 HashMap1. HashMap的内部结构 1 HashMap的底层是一个数组数组的每个元素都是一个链表。链表中的每个元素都是一个个Node节点每个节点都是由 哈希值keyvalue指向下个节点的地址值等几个部分组成的。 2 哈希表是按照一定的规律对对象进行分类管理的加载因子 哈希表中当前元素数量 / 哈希表中桶的总数量当每一个链表(桶)中的平均元素数量过多超过哈希因子时就会进行再哈希。初始size是16扩容的时候mewSizeoldSize*2 3当链表中有新的节点生成时旧的节点会向链表的下端移动而在链表的顶端再生成一个节点所以节点生成的越早越靠近链表的末端。 2. HashMap的特点 1 HashMap可以存储null 键和 null 值但是null 键只能有一个null值可以有多个。 2 HashMap的迭代器是fail-fast的所以在遍历时如果改变了hashMp的结构就会抛出异常。 3 线程不安全。 3. HashMap中的key判断唯一性的原理 1) 先比较两个对象的哈希值是否一样如果不同那么直接判断这两个对象为不一样。 2) 如果两个对象的哈希值相同那么会再调用对象的equals()方法进行比较如果调用equals()方法比较后也相同就会认为这两个对象是相同的如果调用equals()方法得到的结果不同就会认为这两个对象不同。 注意点 1 判断对象的哈希值是否相同是调用的对象的HashCoed()方法如果没有重写对象的HashCoed()方法那么默认调用的是Object对象中的HashCoed()方法而Object对象中的HashCoed()方法的判断比较的是地址值只要地址值不一样都会判断两个对象的哈希值不同。 2很多时候我们希望比较的不是地址值而只是属性值即只要两个对象的属性值完全一样就认为这两个对象一样那么我们就需要重写对象的HashCode()方法和equals()方法。 4. HashMap中的key判断唯一性的原理跟HashSet一模一样具体原因为 1 HashSet内部就是在使用HashMap存储数据HashSet只用到了HashMap中的key。 2) HashSet的add()方法其实就是它内部的一个map调用的put()方法map将添加的值作为key将一个固定值作为value进行存储。5 LinkedHashMap1. 内部结构 1 LinkedHashMap的内部结构和LinkedHashSet一模一样。它的内部也是一个哈希表和一个双向链表。 2 双向链表的作用保证数据的有序性。6 HashTable1. 特点 1 底层采用的是数组链表的形式实现。 2 无论key还是value都不可以是null。 3 线程安全实现线程安全的方式是在修改数据时锁住整个hashtable所以效率比较低。 4 初始size是11扩容是 new size oldsize*21。 5 实现了map接口但是实现是基于Dictionary抽象类的。 6 hashTable 的迭代器不是fail-fast的。7 TreeMap1. 特点 1 底层实现是 红黑树。 2 键按照自然顺序或者自定义比较器的顺序 进行排序。8 CurrentHashMap1. 特点 1 currtentHashMap是一个线程安全的集合。 2 在jdk1.7中currtentHashMap的数据结构是由一个Segment数组和多个HashEtry组成主要实现原理是实现了锁分离的思路来解决多线程的线程安全问题。 3 jdk1.8中currtentHashMap的数据结构是Node数组链表红黑树的结构。并发控制使用的Synchonized和CAS(比较交换)来操作CAS是一种基于乐观锁的操作。 4 高并发下性能优于HashTable。 5不允许null 键 和 null 值。9 hashTable和hashMap的区别1. 继承的父类不同 hashTable继承自Dictionary类 HashMap继承自AbstractMap类 但两者都实现了map,Cloneable,Serializable接口。 2. 线程安全性不同 hasnTable是线程安全的因为它的每个方法都加了synchronize hasnMap是线程不安全的多线程时需要自己添加锁。 3. 是否提供contains()方法 hashMap把contains()方法去掉了 hashTable保留着contains()方法 contains()方法和containsValue()方法相同。 4. key和value是否允许null hashTable的key和value都不允许null如果存入了null值取得时候会报空指针。 hashMap的key和value都允许null。 5. hash值不同 hashTable直接使用对象的HashCode hashMap会重新计算hash值。 6. 数组的初始化和扩容方式不同 HashTable默认容量是11扩容是 oldSize*21 ; HashMap默认是16扩容是 oldSize*210CAS锁1. CAS锁并不是指一个具体的锁而是指一类基于CAS操作实现的锁机制的总称。 2. CAS的全称是Compare-And-Swap(比较并交换)它是一种原子操作意味着在执行过程中不会被任何线程打断。 3. CAS包含3个操作数 1) 内存位置(V) 2) 期望的原值(A) 3) 准备设置的新值(B) 4. CAS的工作流程是 1只有当内存位置V的当前值等于我们预期的原值A的时候处理器才会自动的将该位置的值更新为新值B。 2如果内存位置V的值不等于A说明有其他的线程修改过了那么这次修改操作就会失败并返回当前V的真实值。 3这个操作是原子的所以在执行过程中不会有其他线程能插足修改V的值。 5. CAS锁通常表现为自旋锁它的核心思想是线程通过不断的循环尝试(自旋)用CAS操作去竞争一个表示锁状态的标志位直到成功为止。 6.CAS锁的优点 1高性能(在低竞争情况下)当锁被占用的时间非常短竞争也不激烈时线程通常能在很短的自旋后获得锁避免了线程挂起和上下文切换的巨大开销。 2避免死锁由于是“非阻塞”的线程不会因为拿不到锁而永久阻塞它一直在活跃地尝试。 7.CAS锁的缺点 1CPU空转如果锁被长时间占用竞争线程会一直在循环中消耗CPU资源做无用功。这在高竞争场景下对性能是灾难性的。 2不公平性自旋锁不保证先来的线程先获得锁任何一个在自旋的线程都有可能抢到锁。 3只能用于单机/多核CPU它的实现依赖于多核CPU的缓存一致性协议如MESI在单核CPU上自旋没有意义因为持有锁的线程无法被调度运行。6. 容器线程安全性对比1. 线程安全的容器 CurrentHashMap , CurrentHashSet , SynchronizedList CoppyOnWriteArrayList , CopyOnWriteArraySet vectory , hashTable 是线程安全的 2. 线程不安全的容器 ArrayList , hashMap 都是线程不安全的 如果想线程安全那么可以 a. 自己加上synchronized关键字 b. 初始化的时候使用 Collections.synchronizedList()方法