2 haveferrair HaveFerrair 于 2016.03.27 21:15 提问

Java HashMap的get(),put()算法时间复杂度

Java7和Java8的HashMap的put(),get()方法的时间复杂度是啥?还请从平均,最好,最坏的角度分析。谢谢

3个回答

caozhy
caozhy   Ds   Rxr 2016.03.27 22:25
已采纳

最优情况,hash不碰撞,O(1),典型情况,近似是O(1),因为几乎没有碰撞,最坏情况,O(N),也就是所有的hash都一样,那么退化为线性查找

wojiushiwo945you
wojiushiwo945you   Ds   Rxr 2016.03.27 21:27

hashmap的底层是两个数组,put最坏查找N次,get也是如此 。

love_register
love_register   2016.03.27 23:31

理想的是On,容量大小和分布是不是均匀都会有影响

love_register
love_register 理想O1,写错了
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
java HashMap在不发生冲突的情况下get(key)时间复杂度是o(1)
HashMap在不发生冲突的情况下时间复杂度是o(1) 今天上课,老师布置了一道java题
HashMap的put、get方法分析与Hash冲突的分析、解决
HashMap的put、get方法分析与Hash冲突的分析、解决
HashMap中put与get的实现
      java容器中,Map是用来存储键值对的,Map是一个接口,java为他实现了好几种实现,有HashMap、LinkedHashMap、TreeMap、WeakHashMap等,一般情况下,HashMap是最常用的,因为他的存取速度最快,这和他存取的方法有关。下面我们来看看HashMap是如何实现快速存取的。       下面是《thinkinjava》中关于Map的一个实现:
HashMap的put和get方法原理
概述JAVA中的数组,在添加或者删除元素的时候,都会复制一个新数组,比较耗内存。但是数组的遍历则是非常高效的。链表则是相反, 遍历慢(需要遍历数组,一直找到值相等的元素才算找到),而添加和删除元素代价低。有没有办法结合两者的特点,做到寻找元素快,插入元素或者删除元素代价低呢?答案是利用哈利表。HashMap put操作当使用HashMap的put方法的时候,有两个问题要解决:1、长度为16的数组中
了解HashMap的get和put内部的工作原理,需要理解透Java HashMap的原理
了解HashMap的get和put内部的工作原理,需要理解透Java HashMap的原理,今天我们单说get和put 的工作原理。 一、Put : 让我们看下put方法的实现: /**   * Associates the specified value with the specified key in this map. If the  
Java HashMap的数据结构以及put和get方法
1 HashMap的数据结构 HashMap实际上是一个链表数组,也就是最外层是数组,数组的元素是链表。    2 HashMap的put方法: 源代码如下:   public V put(K key, V value) { //1 如果Key为Null 则put到Key为null的位置 if (key == null) return p
HashMap put() get()
<br />Map用 put(k,v) / get(k),还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。 <br />  HashMap会利用对象的hashCode来快速找到key。 <br />    *  hashing <br />      哈希码就是将对象的信息经过一些转变形成一个独一无二的int值,这个值存储在一个array中。 <br />      我们都知道所有存储结构中,array查找速度是最快的。所以,可以加速查找。 <b
HashMap.put/get方法
HashMap 是以key,value的键值对形式存储数据,key不能重复,put源码如下: public V put(K key, V value) {     if (key == null)         return putForNullKey(value);     //key不为空时     int hash = hash(key); //先获取
基于源码(jdk1.7)对HashMap的get()和put()的小结
HashMap的概述 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collecti
JDK源码之解读hashMap 的put和get方法的实现原理
JDK源码之解读hashMap 的put和get方法的实现原理 1,put              对于方法hashmap.put(K,V),首先是把k处理,通过hashcode方法处理得到K对应的hash=hash(K).              再调用h & (length-1)得到数组下标i. 最后调用createEntry(hash, key, value, i)方法,把