刷题upupup【Java中HashMap、HashSet用法总结】

时间:2024-01-05 16:02:49

HashMap:

常用操作

1. containsKey() 判断HashMap是否包含key

2. containsValue() 判断HashMap是否包含“值为value”的元素

3. get() 获取key对应的value

4. put() 让HashMap对象可以通过put()将“key-value”添加到HashMap中

5. remove() 删除“键为key”元素

遍历方式

1.  在for-each循环中使用entries来遍历

 Map<Integer, Integer> map = new HashMap<Integer, Integer>();  

 for (Map.Entry<Integer, Integer> entry : map.entrySet()) {  

     System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());  

 }  

2.  在for-each循环中遍历keys或values

Map<Integer, Integer> map = new HashMap<Integer, Integer>();  

//遍历map中的键  

for (Integer key : map.keySet()) {  

    System.out.println("Key = " + key);  

}  

//遍历map中的值  

for (Integer value : map.values()) {  

    System.out.println("Value = " + value);  

}  

3.  使用Iterator遍历

 Map<Integer, Integer> map = new HashMap<Integer, Integer>();  

 Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();  

 while (entries.hasNext()) {  

     Map.Entry<Integer, Integer> entry = entries.next();  

     System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());  

 }  

HashSet

常用操作

add(Object o);往set添加元素

clear();移除所有元素

size();返回元素的个数

remove(Object o); 如果指定元素存在于此set中,移除

isEmpty(); 如果set不包含任何元素,返回true

contains(Object o) 如果此set包含指定元素,返回true

HashSet遍历

使用for循环遍历

Set<String> set = new HashSet<String>();
for (String str : set) {
System.out.println(str);
}

区别:

HashSet只存key

HashMap、HashTable存key - value

HashTable 多线程同时访问同一个HashTable更安全,因为有线程加锁

HashMap原理以及时间复杂度

首先根据hashCode()做hash,然后确定bucket的index;

如果bucket的节点的key不是我们需要的,则通过keys.equals()在链中找。

put()

对key的hashCode()做hash,然后再计算index;

如果没碰撞直接放到bucket里;

如果碰撞了,以链表的形式存在buckets后;

如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树;

如果节点已经存在就替换old value(保证key的唯一性)

如果bucket满了(超过load factor*current capacity),就要resize。

get()

bucket里的第一个节点,直接命中;

如果有冲突,则通过key.equals(k)去查找对应的entry.若为树,则在树中通过key.equals(k)查找,O(logn);若为链表,则在链表中通过key.equals(k)查找,O(n)。

HashMap的查找时间复杂度只有在最理想的情况下(链表长度为1)才会为O(1),O(size of key)

Avg O(1), worst O(n) time 和O(n) space.

每一次存或者取,通过计算一个hash function获得key的unique hash值, 这部分是O(1)的. 正常情况就只需要这么多,如果有collision的话,就是两个key 算出来的hash值是一样的,那就是linear 的complexity, 因为一个key里面有两个值, 所以worst的情况O(n), 然而这个几率非常小, 多次都collide的几率更小.

Space的话就是每多一个key-value pair,就要allocate一个space,所以是O(n).

在Java 8之前的实现中是用链表解决冲突的,在产生碰撞的情况下,进行get时,两步的时间复杂度是O(1)+O(n)

因此在Java 8中,利用红黑树替换链表,这样复杂度就变成了O(1)+O(logn)