赞
踩
目录
为什么长度为8转化为红黑树,不是一开始就是红黑树或者链表呢?
类
我们口中所说的集合类的类型主要为三种:set(集合),map(映射),list(列表)
集合类是通过两个接口来实现的
1.Collection接口,list和set实现了这个接口
2.Map接口,map实现了这个接口
大体有
自己根据源码总结的流程图为
常见的数据结构
我们常见的数据结构有三种
1.数组结构
2.链表结构
3.哈希表结构
存储区间连续、内存占用严重、空间复杂度大、大小固定,不易扩展
随机读取和修改效率高,因为数组是连续的,随机访问性强,查找速度快
插入和删除效率低,因为插入数据,这个位置后面的数据在内存中都要往后移动,且大小固定,不易动态扩展
存储区间离散、占用内存宽松、空间复杂度小、大小不固定,易于扩展
插入删除速度快,内存利用效率高,没有固定大小,扩展灵活
查询较复杂,不能随机查找,每次都是从第一个开始遍历,查询效率低
结合数组结构和链表结构的优点,从而实现了查询修改效率高,插入和删除效率也高的一种数据结构
HashMap就是这样一种数据结构
因为增删是在链表上进行的,查询是在数组上进行的
参考文章:
HashMap底层实现原理解析_苟且偷生的程序员的博客-CSDN博客_hashmap底层实现原理
List
List(列表)中,分为三大部分
1. ArrayList
2.Vector
3.LinkedList
底层数据结构为数组array,查询速度快,增删改慢,因为是一种类似数组的形式进行存储,所以随机访问的速度极快
- public class Test01 {
- public static void main(String[] args) {
- ArrayList<String> arrayList = new ArrayList<>(); //创建一个arrayList对象
- ArrayList<String> arrayList1 = new ArrayList<>(10); //创建一个长度为10的arrayList
- arrayList.add("123"); //向arrayList集合中添加一个元素,可以有选择的返回一个boolean类型
- boolean add = arrayList.add("456"); //返回boolean类型
- String s = arrayList.get(1); //返回下标为1的元素(下标从0开始)
- String set = arrayList.set(1, "789"); //将下标为i的元素替换为"789"并返回被替换的元素
- int size = arrayList.size(); //返回元素个数
- String remove1 = arrayList.remove(0); //删除下标为0的元素(下标从0开始),返回被删除的元素
- boolean remove = arrayList.remove("123"); //删除集合中第一次出现的指定元素,返回boolean类型
- ArrayList<Integer> integerArrayList = new ArrayList<>();
- ArrayList<Integer> integerArrayList1 = new ArrayList<>();
- integerArrayList.add(123);
- integerArrayList.add(123);
- integerArrayList.add(456);
- integerArrayList1.add(123);
- System.out.println(integerArrayList);
- integerArrayList.removeAll(integerArrayList1); //从集合integerArrayList中删除integerArrayList1的所有元素,不是只删除第一个,是删除所有的
- System.out.println(integerArrayList);
- arrayList.clear(); //清除集合中的元素
- boolean empty = arrayList.isEmpty(); //判断集合是否为空
- boolean contains = arrayList.contains("123"); //判断集合中是否有“123”这个元素,返回boolean类型
- arrayList.add("123");
- arrayList.add("456");
- Iterator<String> iterator = arrayList.iterator(); //返回集合首地址的迭代器,迭代器指向的是下标为0的前一个地址(?)
- boolean b = iterator.hasNext(); //判断iterator是否存在下一个元素,返回boolean
- String next = iterator.next(); //先将指针移动到下一个位置,然后再获取值
- while(iterator.hasNext()) {
- System.out.println(iterator.next());
- }
- }
- }
这里需要注意,迭代器iterator返回的是ArrayList下标为0的元素地址的前一个
底层的数据结构是是数组array,与ArrayList相同,查询速度快,增删改慢
- public class Test01 {
- public static void main(String[] args) {
- Vector<String> Vector = new Vector<>(); //创建一个Vector对象
- Vector<String> Vector1 = new Vector<>(10); //创建一个长度为10的Vector
- Vector.add("123"); //向Vector集合中添加一个元素,可以有选择的返回一个boolean类型
- boolean add = Vector.add("456"); //返回boolean类型
- String s = Vector.get(1); //返回下标为1的元素(下标从0开始)
- String set = Vector.set(1, "789"); //将下标为i的元素替换为"789"并返回被替换的元素
- int size = Vector.size(); //返回元素个数
- String remove1 = Vector.remove(0); //删除下标为0的元素(下标从0开始),返回被删除的元素
- boolean remove = Vector.remove("123"); //删除集合中第一次出现的指定元素,返回boolean类型
- Vector.clear(); //清除集合中的元素
- boolean empty = Vector.isEmpty(); //判断集合是否为空
- boolean contains = Vector.contains("123"); //判断集合中是否有“123”这个元素,返回boolean类型
- Vector.add("123");
- Vector.add("456");
- Iterator<String> iterator = Vector.iterator(); //返回集合首地址的迭代器,迭代器指向的是下标为0的前一个地址(?)
- boolean b = iterator.hasNext(); //判断iterator是否存在下一个元素,返回boolean
- String next = iterator.next(); //先将指针移动到下一个位置,然后再获取值
- while(iterator.hasNext()) {
- System.out.println(iterator.next());
- }
- }
- }
与ArrayList相同
ArrayList线程不同步,Vector线程安全,因为每个方法上都加上了synchronized,但是Vector的效率小于ArrayList
Vector安全但是效率低,因为加锁和放锁的过程中,在系统中是有开销的
ArrayList
无synchronized
Vectoer
有synchronize
底层数据接口使用链表,增删改速度快,查询稍慢
LinkedList是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。
- public class Test01 {
- public static void main(String[] args) {
- LinkedList<String> LinkedList = new LinkedList<>(); //创建一个LinkedList对象,无法初始化大小
- LinkedList.add("123"); //向LinkedList链表中添加一个元素,可以有选择的返回一个boolean类型
- boolean add = LinkedList.add("456"); //返回boolean类型
- LinkedList.addFirst("123"); //在头部插入
- LinkedList.addLast("123"); //在尾部插入
- String s = LinkedList.get(1); //返回下标为1的元素(下标从0开始)
- String first = LinkedList.getFirst(); //获取第一个下标的元素
- String last = LinkedList.getLast(); //获取最后一个下标的元素
- String set = LinkedList.set(1, "789"); //将下标为i的元素替换为"789"并返回被替换的元素
- int size = LinkedList.size(); //返回元素个数
- String remove1 = LinkedList.remove(0); //删除下标为0的元素(下标从0开始),返回被删除的元素
- boolean remove = LinkedList.remove("123"); //删除链表中第一次出现的指定元素,返回boolean类型
- String s1 = LinkedList.removeFirst(); //删除链表中的第一个元素
- String s2 = LinkedList.removeLast(); //删除链表的最后一个元素
- boolean b1 = LinkedList.removeFirstOccurrence("123"); //删除链表中第一次出现"123"所在位置的元素
- boolean b2 = LinkedList.removeLastOccurrence("123"); //删除链表中最后一次出现"123"所在位置的元素
- LinkedList.clear(); //清除链表中的元素
- boolean empty = LinkedList.isEmpty(); //判断链表是否为空
- boolean contains = LinkedList.contains("123"); //判断链表中是否有“123”这个元素,返回boolean类型
- LinkedList.add("123");
- LinkedList.add("456");
- Iterator<String> iterator = LinkedList.iterator(); //返回链表首地址的迭代器,迭代器指向的是下标为0的前一个地址(?)
- boolean b = iterator.hasNext(); //判断iterator是否存在下一个元素,返回boolean
- String next = iterator.next(); //先将指针移动到下一个位置,然后再获取值
- while(iterator.hasNext()) {
- System.out.println(iterator.next());
- }
- }
- }
Set
Set接口有三个主要的实现类
1.HashSet
3.TreeSet
set的实现类(HashSet,LinkedHashSet,TreeSet)都是线程不安全的, 解决方法
- class E{
- public static void main(String[] args) {
- Set<Integer> set = new HashSet<>();
- Set<Integer> integers = Collections.synchronizedSet(set); //这里是Collections,不是Collection,一个是类,一个是接口
- }
- }
Set最常用的实现类,底层数据结构运用Hash(散列/哈希)算法,底层也是用数组实现
- public class Test02 {
- public static void main(String[] args) {
- HashSet<String> HashSet = new HashSet<>(); //创建一个HashSet对象,无法初始化大小
- HashSet.add("123"); //向HashSet链表中添加一个元素,可以有选择的返回一个boolean类型
- boolean add = HashSet.add("456"); //返回boolean类型
- int size = HashSet.size(); //返回元素个数
- boolean remove1 = HashSet.remove(0); //删除下标为0的元素(下标从0开始),返回被删除的元素
- boolean remove = HashSet.remove("123"); //删除链表中第一次出现的指定元素,返回boolean类型
- HashSet.clear(); //清除链表中的元素
- boolean empty = HashSet.isEmpty(); //判断链表是否为空
- boolean contains = HashSet.contains("123"); //判断链表中是否有“123”这个元素,返回boolean类型
- HashSet.add("123");
- HashSet.add("456");
- Iterator<String> iterator = HashSet.iterator(); //返回链表首地址的迭代器,迭代器指向的是下标为0的前一个地址(?)
- boolean b = iterator.hasNext(); //判断iterator是否存在下一个元素,返回boolean
- String next = iterator.next(); //先将指针移动到下一个位置,然后再获取值
- while(iterator.hasNext()) { //迭代器遍历
- System.out.println(iterator.next());
- }
- for (String str: HashSet) { //for循环遍历
- System.out.println(str);
- }
- }
- }
继承和HashSet类,底层也是哈希表结构,但是为了保持数据先后添加的顺序,所以又加了链表结构,因为多加了一层数据结构,所以效率低,不建议使用
- public class Test02 {
- public static void main(String[] args) {
- LinkedHashSet<String> LinkedHashSet = new LinkedHashSet<>(); //创建一个LinkedHashSet对象,无法初始化大小
- LinkedHashSet.add("123"); //向LinkedHashSet链表中添加一个元素,可以有选择的返回一个boolean类型
- boolean add = LinkedHashSet.add("456"); //返回boolean类型
- int size = LinkedHashSet.size(); //返回元素个数
- boolean remove1 = LinkedHashSet.remove(0); //删除下标为0的元素(下标从0开始),返回被删除的元素
- boolean remove = LinkedHashSet.remove("123"); //删除链表中第一次出现的指定元素,返回boolean类型
- LinkedHashSet.clear(); //清除链表中的元素
- boolean empty = LinkedHashSet.isEmpty(); //判断链表是否为空
- boolean contains = LinkedHashSet.contains("123"); //判断链表中是否有“123”这个元素,返回boolean类型
- LinkedHashSet.add("123");
- LinkedHashSet.add("456");
- Iterator<String> iterator = LinkedHashSet.iterator(); //返回链表首地址的迭代器,迭代器指向的是下标为0的前一个地址(?)
- boolean b = iterator.hasNext(); //判断iterator是否存在下一个元素,返回boolean
- String next = iterator.next(); //先将指针移动到下一个位置,然后再获取值
- while(iterator.hasNext()) { //迭代器遍历
- System.out.println(iterator.next());
- }
- for (String str: LinkedHashSet) { //for循环遍历
- System.out.println(str);
- }
- }
- }
1.在HashSet插入中,不保留顺序,这意味着元素的插入顺序不需要与元素的检索顺序相同。
在LinkedHashSet中,保留插入顺序,这意味着元素的插入顺序必须与元素的检索顺序相同。
2.HashSet的效率高于LinkedHashSet
Set接口的实现类,实现了SortSet接口,底层采用红黑树算法,TreeSet只能存储相同类型的对象的引用
- public class Test02 {
- public static void main(String[] args) {
- TreeSet<String> TreeSet = new TreeSet<>(); //创建一个TreeSet对象,无法初始化大小
- TreeSet.add("123"); //向TreeSet链表中添加一个元素,可以有选择的返回一个boolean类型
- boolean add = TreeSet.add("456"); //返回boolean类型
- int size = TreeSet.size(); //返回元素个数
- boolean remove1 = TreeSet.remove(0); //删除下标为0的元素(下标从0开始),返回被删除的元素
- boolean remove = TreeSet.remove("123"); //删除链表中第一次出现的指定元素,返回boolean类型
- TreeSet.clear(); //清除链表中的元素
- boolean empty = TreeSet.isEmpty(); //判断链表是否为空
- boolean contains = TreeSet.contains("123"); //判断链表中是否有“123”这个元素,返回boolean类型
- TreeSet.add("123");
- TreeSet.add("456");
- Iterator<String> iterator = TreeSet.iterator(); //返回链表首地址的迭代器,迭代器指向的是下标为0的前一个地址(?)
- boolean b = iterator.hasNext(); //判断iterator是否存在下一个元素,返回boolean
- String next = iterator.next(); //先将指针移动到下一个位置,然后再获取值
- while(iterator.hasNext()) { //迭代器遍历
- System.out.println(iterator.next());
- }
- for (String str: TreeSet) { //for循环遍历
- System.out.println(str);
- }
- }
- }
List和Set的区别
对于ArrayList和HashSet来说
ArrayList是有序的
HashSet是无序的
ArrayList是可重复的
HashSet是不可重复的
ArrayList可以有多个null元素
HashSet只能有一个null元素
ArrayList可以使用迭代器取出所有元素,也可以通过get(index)获取制定下表的元素
Set只能通过迭代器获得所有元素,然后逐个遍历
Map
Map接口有三个主要的实现类
1.HashMap
2.TreeMap
3.HashTable
哈希表的实现原理,先拿一个数组表示位桶,每个位桶在用链表存储数据,当数据超过阈值8,且数组长度超过64的时候,会将数据转化为红黑树来存储数据,当数据个数小于6的时候,红黑树会退化为链表
所以HashMap底层的数据结构是数组+链表+红黑树
首先我们知道,链表的平均查找的时间复杂度是O(n),红黑树有和链表不一样的查找性能,由于红黑树有自平衡的特点,所以始终可以将查找的时间复杂度控制在O(logn)
至于为什么不一开始就是用红黑树,是因为
对于红黑树来说,虽然查询成本低,但是新增的成本高
对于链表来说,虽然查询成本高,但是新增的成本低
最初链表还不是很长,所以O(n)和O(logn)的区别不大,如果长度过长,这种区别就回有多体现所以为了提高查找性能,要把链表转化为红黑树
- public class Test03 {
- public static void main(String[] args) {
- HashMap<String, Integer> hashMap = new HashMap(); //新建一个HashMap
- hashMap.put("123",1); //将值存放到HashMap中
- Integer integer = hashMap.get("123"); //根据键获取值
- int size = hashMap.size(); //获取HashMap大小
- hashMap.clear(); //清空HashMap
- boolean empty = hashMap.isEmpty(); //判断是否为空
- Integer remove = hashMap.remove("123"); //根据键删除值,并返回
- Collection<Integer> collection;
- collection = hashMap.values(); //以Collection的形式返回HashMap集合中所有value组成的值
- System.out.println(collection);
- Set<String> strings = hashMap.keySet(); //以Set的形式返回键的集合
- Iterator<String> iterator1 = strings.iterator(); //与keySet合用,获得迭代器
- Set<Map.Entry<String, Integer>> entries = hashMap.entrySet(); //将HashMap中的每个键值转化为Entry对象并返回Set集合
- Iterator<Map.Entry<String, Integer>> iterator = entries.iterator(); //与entrySet合用,返回迭代器
- while(iterator.hasNext()){
- Map.Entry<String, Integer> next = iterator.next();
- System.out.println(next.getKey()); //获得键
- System.out.println(next.getValue()); //获得值
- }
- }
- }
实现了SortedMap接口,是一个有序的集合,底层是红黑树结构,每一个key-value都作为一个红黑树的节点
- public class Test03 {
- public static void main(String[] args) {
- TreeMap<String, Integer> TreeMap = new TreeMap(); //新建一个TreeMap
- TreeMap.put("123",1); //将值存放到TreeMap中
- Integer integer = TreeMap.get("123"); //根据键获取值
- int size = TreeMap.size(); //获取TreeMap大小
- TreeMap.clear(); //清空TreeMap
- boolean empty = TreeMap.isEmpty(); //判断是否为空
- Integer remove = TreeMap.remove("123"); //根据键删除值,并返回
- Collection<Integer> collection;
- collection = TreeMap.values(); //以Collection的形式返回TreeMap集合中所有value组成的值
- System.out.println(collection);
- Set<String> strings = TreeMap.keySet(); //以Set的形式返回键的集合
- Iterator<String> iterator1 = strings.iterator(); //与keySet合用,获得迭代器
- Set<Map.Entry<String, Integer>> entries = TreeMap.entrySet(); //将TreeMap中的每个键值转化为Entry对象并返回Set集合
- Iterator<Map.Entry<String, Integer>> iterator = entries.iterator(); //与entrySet合用,返回迭代器
- while(iterator.hasNext()){
- Map.Entry<String, Integer> next = iterator.next();
- System.out.println(next.getKey()); //获得键
- System.out.println(next.getValue()); //获得值
- }
- }
- }
HashMap是通过hashcode对内容进行快速查找的,HashMap中的元素是没有顺序的
TreeMap所有元素是由某一固定顺序的,如果需要的到一个有序结构,就应该使用TreeMap
HashMap和TreeMap都是线程不安全的
HashMap继承AbstractMap类,覆盖了hashcode和equals方法
ThreeMap继承SortedMap类,保持键的有序顺序
HashMap基于hash表实现,底层数据结构为数组+链表+红黑树
TreeMap基于红黑树实现,底层数据结构为红黑树
继承了Map接口,和HashMap类似
HashMap继承AbstractMap
Hashtable继承Dicitionary(已废弃?)
HashTable比HashMap多提供elments和contians方法
HashTable既不支持Null key也不支持Null value
HashMap中,Null可以作为key,这样的键只有一个
HashTable线程安全,但是效率低
HashMap线程不安全,但是效率高
HashTable默认初始化大小为11,每次扩充容量变为原来的2n+1
HashMap默认初始化大小为16,每次扩充容量变为2倍
HashTable直接使用对象的hashCode,计算时需要进行除法运算
HashMap为了提高计算效率,将哈希表的大小固定为2的幂,不用做除法,只需要位运算即可
HashMap虽然效率高,但是Hash冲突也增加了
参考文章
HashMap 与HashTable的区别_wangxing233的博客-CSDN博客_hashmap和hashtable的区别
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。