java–ArrayList、LinkedList、HashSet、HashMap、HashTable、Collection、Collections详解

时间:2020-6-30 作者:admin


1.ArrayList

ArrayList是List接口的实现类,一种大小可变数组,随着元素的增多,容量会自动扩充,默认初始容量值是10,也可以自己指定初始容量

采用的数据结构:数组
(线性表:数组、链表、队列、栈
非线性表:二叉树、堆、图等)

ArrayList优点:
查询速度快
ArrayList缺点:
新增和删除元素比较慢

查询速度快的原因:
ArrayList底层是数组实现的,根据下标查询,不需要比较,查询方式为,首地址+(元素长度*下标),基于这个位置读取相应的字节数,所以非常快;

新增和删除慢的原因:
增删会带来元素的移动,增加数据会向后移动,删除数据会向前移动,所以影响效率

适用场景:
如果应用程序对数据有较多的随机访问使用ArrayList较好

2.LinkedList

LinkedList也是List接口的实现类,和ArrayList功能类似,但LinkedList新增几个功能 ,如addFirst(),addLast(),getFirst(),getLast()等

数据结构:双向链表

链式存储,在内存中不是连续存储的,每个元素存储包括三部分,前一个元素的内存地址、数据部分、后一个元素内存地址,因此在进行元素的新增和删除时效率比较高,但查询时比较慢
链式存储方式与数组的连续存储方式相比,其实对内存的利用率更高

3.HashSet

HashSet是Set接口的实现类,最大的特点就是内部元素无序、并且不能重复(重复添加的话会默认覆盖上一个相同的元素),默认初始容量16

HashSet数据结构:哈希表(数组+链表)

HashSet存储原理:

Set set=new HashSet();
set.add(object);

存储过程为:
定义x=object.hashCode,得到obj对象的哈希码x,再对x进行hash散列运算,对数组长度进行求余,假如长度为20,则返回一个0-19之间的值,然后这个值就是存在HashSet数组中的下标。如果下标位置没有对象,则把object加到该位置;如果已有对象,则用equals判断两对象是否相等,相等则舍弃object,不相等,则把object以链表的方式加在该对象下面

原则1:让equals相等的对象返回相同的hashCode(为了过滤掉相等的元素)
原则2:尽量保证equals不相同的对象返回不同的hashCode(为了添加不同的元素)
存储过程图解如下:
java--ArrayList、LinkedList、HashSet、HashMap、HashTable、Collection、Collections详解
HashSet的add()方法底层使用的是HashMap的存储方式,看源码可以知道
java--ArrayList、LinkedList、HashSet、HashMap、HashTable、Collection、Collections详解
add()方法
java--ArrayList、LinkedList、HashSet、HashMap、HashTable、Collection、Collections详解

4.HashMap

map是存放键值对的。
HashMap是Map接口的实现类,也是采用了hash算法。

其实向HashSet中放值,就是向HashMap中放值

Key不可以一样,如果key一样,在内存中存储的位置相同,后一个会把前一个key覆盖,value可以一样
key和value均可以为null
HashMap的存储键的过程和HashSet一样,不过HashMap在根据key获取value时的原理如下:
前面也是根据对象获取哈希码,进行哈希运算求下标(哈希码%容量),如果下标位置只有一对key-value,就直接取得value,如果有多个key-value键值对,然后再根据key获取value。

HashMap的数据结构
数组+单链表(数组中的每个元素都是单链表的头节点)
使用链表的原因是解决哈希冲突的(即不同的key映射到了数组的同一位置处,就将其放入单链表中)
java--ArrayList、LinkedList、HashSet、HashMap、HashTable、Collection、Collections详解
ConcurrentHashMap

HashMap是线程不安全的
HashTable是HashMap的兄弟。HashMap跟HashTable用法基本一样

它们两个区别就是HashTable是线程安全的

线程安全:
10个人同时操作HashTable,只有一个人操作,剩下的九个人等待。操作完毕后,剩下的9个人中的一个人操作HashTable,剩下8个人等待

线程不安全:
10个人同时操作

例子: 第一个人拿原始值, 如10
第二个人修改原始值 10-》20

如果二个人修改了原始值,会造成后面的人再拿数据时,会拿到第二个人修改后的数据(脏数据)

5.HashTable

HashTable和HashMap功能类似,都是用来保存键值对,但两者之间又有区别
区别:
1.HashTable中不允许保存null的,而HashMap可以保存空的null和value
2…HashTable线程安全
HashMap线程不安全
3.Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类。但二者都实现了Map接口

6.Collection

collection是list和set接口的父接口,是一个集合接口

7.Collections

Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化,就像一个工具类
常用方法如下:
Collections.sort()
Collections.reverse()
Collections.binarySearch()方法
为二分法查找,所以数组必须是有序的或者是用sort()方法排序之后的。
binarySearch(Object[], Object key)
方法的object[]参数是要查找的数组,key参数为要查找的key值。

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:87074139@qq.com 进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。