List、Map、Set三个接口存取元素时,各有什么特点

Stella981
• 阅读 743

List接口以特定索引来存取元素,可以有重复元素

Set接口不可以存放重复元素(使用equals方法区分是否重复)

Map接口保存的是键值对(key-value-pair)映射,映射关系可以是一对一或者多对一(key唯一)

Set和Map容器都有基于哈希存储和排序树的两种实现版本。基于哈希存储的版本的实现理论存取时间复杂度是O(1),而基于排序树版本的的实现在插入或者删除元素时会按照元素或者元素的key构成排序树从而达到去重和排序的效果

哈希存储的版本的实现理论存取时间复杂度是O(1)

HashMap源码:

put方法

 1 public V put(K key, V value) {  
 2     // HashMap允许存放null键和null值。  
 3     // 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。  
 4     if (key == null)  
 5         return putForNullKey(value);  
 6     // 根据key的keyCode重新计算hash值。  
 7     int hash = hash(key.hashCode());  
 8     // 搜索指定hash值在对应table中的索引。  
 9     int i = indexFor(hash, table.length);  
10     // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素。  
11     for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
12         Object k;  
13         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
14             V oldValue = e.value;  
15             e.value = value;  
16             e.recordAccess(this);  
17             return oldValue;  
18         }  
19     }  
20     // 如果i索引处的Entry为null,表明此处还没有Entry。  
21     modCount++;  
22     // 将key、value添加到i索引处。  
23     addEntry(hash, key, value, i);  
24     return null;  
25 }

get方法

 1 public V get(Object key) {  
 2         if (key == null)  
 3             return getForNullKey();  
 4         int hash = hash(key.hashCode());  
 5         for (Entry<K,V> e = table[indexFor(hash, table.length)];  
 6              e != null;  
 7              e = e.next) {  
 8             Object k;  
 9             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
10                 return e.value;  
11         }  
12         return null;  
13 }

该过程一共分四步:

  1. 根据key的keyCode重新计算hash值
  2. 搜索指定hash值在对应table中的索引
  3. 遍历键值对的链表,根据key找到对应的键值对
  4. 从键值对中获取value值

  这四步中,1/2/4每一步的时间复杂度都是O(1),但是第3步是for循环,时间复杂度是O(n),想要保证存取时间复杂度是O(1),那么只有键值对链表长度是1,也就是只有那个hash算法尽量减少冲突,才能使链表长度尽可能短,理想状态为1所以HashMap的查找时间复杂度只有在最理想的情况下才会为O(1)

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
5个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
java中map接口hashMap以及Enty之间的用法和关系
java中map接口hashMap以及Enty之间的转换首先说的是map接口:Map提供了一种映射关系,其中的元素是以键值对(keyvalue)的形式存储的,能够实现根据key快速查找value;建(key值)不可重复,value值可以重复,一个value值可以和很多key值形成对应关系,每个建最多只能映射到一个值。Ma
Wesley13 Wesley13
3年前
Java集合面试题
CollectionSet和hashCode以及equals方法的联系Set内存放的元素为什么不可以重复,内部是如何保证和实现的?List和Set区别List和Map区别Arraylist与LinkedList区别ArrayList与Vector区别Arraylist与LinkedList默认空间是
Stella981 Stella981
3年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Stella981 Stella981
3年前
HashSet和TreeSet
 Set是java中一个不包含重复元素的collection。更正式地说,set不包含满足e1.equals(e2)的元素对e1和e2,并且最多包含一个null元素。正如其名称所暗示的,此接口模仿了数学上的_set_抽象。HashSet与TreeSet都是基于Set接口的实现类。其中TreeSet是Set的子接口Sor
Wesley13 Wesley13
3年前
Java集合之Map接口
Map使用键值对来存储数据,将键映射到值对象,一个映射不能包含重复的键,每一个键最多只能映射到一个值。Map接口的具体实现类:HashMap,Hashtable,TreeMap,LinkedHashMap  1)HashMap  基于哈希表(哈希表学习地址)的Map接口实现。允许使用null值和null键,不保证映射的顺序,特别是不保证顺序恒
Wesley13 Wesley13
3年前
Java容器——Set和顺序存储
  当Set使用自己创建的类型时,存储的顺序如何维护,在不同的Set实现中会有不同,而且它们对于在特定的Set中放置的元素类型也有不同的要求:Set(interface)存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set和Collection具有完全一样的接口,但S
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究