Java笔记（七）HashMap和HashSet
HashMap和HashSet
一）HashMap
1.Map接口
interface Map<K,V> {int size();//查看Map中的鍵值對(duì)個(gè)數(shù)boolean isEmpty();//是否為空boolean containsKey(Object key);//是否包含某個(gè)鍵boolean containsValue(Object value);//是否包含某個(gè)值V get(Object key);//根據(jù)鍵獲取值，沒(méi)找到返回nullV put(K key, V value);//保存鍵值對(duì)，如果原來(lái)有key，則覆蓋并返回原來(lái)的值，原來(lái)沒(méi)有這個(gè)鍵返回nullV remove(Object key);//根據(jù)鍵刪除鍵值對(duì)，返回key原來(lái)的值，如果不存在，返回nullvoid putAll(Map<? extends K,? extends V> m);//保存m中所有的鍵值對(duì)到當(dāng)前mapvoid clear();//清空Map中的所有鍵值對(duì)Set<K> keySet();//獲取Map中所有鍵的集合Collection<V> values();//獲取Map中所有值的集合Set<Map.Entry<K, V>> entrySet();//獲取Map中所有的鍵值對(duì)interface Entry<K,V> { //嵌套接口表示一個(gè)鍵值對(duì)K getKey();//獲取鍵V getValue();//獲取值V setValue(V value);//設(shè)置值boolean equals(Object o);int hashCode();}boolean equals(Object o);int hashCode();}keySet()、values()、entrySet()有一個(gè)共同特點(diǎn)，它們返回的都是視圖，
不是復(fù)制值，基于返回值的修改都會(huì)修改Map自身。例如：
map.keySet().clear();//會(huì)刪除所有鍵值對(duì)2.HashMap
構(gòu)造方法：
public HashMap(int initialCapacity) public HashMap(int initialCapacity, float loadFactor) public HashMap(Map<? extends K, ? extends V> m)主要實(shí)例變量：
static final Entry<?,?>[] EMPTY_TABLE = {}; //table是一個(gè)Entry類型的數(shù)組，稱為哈希表或者哈希桶， //其中每個(gè)元素指向一個(gè)單向鏈表，鏈表中的每個(gè)節(jié)點(diǎn)表示一個(gè)鍵值對(duì) transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; transient int size; //實(shí)際鍵值對(duì)個(gè)數(shù) int threshold;//表示閾值，當(dāng)鍵值對(duì)個(gè)數(shù)size大等于該值時(shí)考慮擴(kuò)展 threshold = table.length * ?loadFactor final float loadFactor;Entry是一個(gè)內(nèi)部類，構(gòu)造方法：
static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next; //指向下一個(gè)節(jié)點(diǎn)int hash; //key的hash值Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h; //存儲(chǔ)hash值是為了在比較的時(shí)候加快速度}}當(dāng)添加鍵值對(duì)后，table就不是空表了，它會(huì)隨著鍵值對(duì)的添加進(jìn)行擴(kuò)展，擴(kuò)展的策略類似于ArrayList.
默認(rèn)構(gòu)造方法：
public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } //其中DEFAULT_INITIAL_CAPACITY=16，DEFAULT_LOAD_FACTOR=0.75調(diào)用了：
public HashMap(int initialCapacity, float loadFactor) {this.loadFactor = loadFactor;threshold = initialCapacity; }put方法：
public V put(K key, V value) {if(table == EMPTY_TABLE) {inflateTable(threshold);}if(key == null)return putForNullKey(value);int hash = hash(key); //計(jì)算key的hash值int i = indexFor(hash, table.length); //計(jì)算應(yīng)該將這個(gè)鍵值對(duì)放入table中的哪個(gè)位置//注意table是一個(gè)單向鏈表，現(xiàn)在在這個(gè)鏈表中查找是否已經(jīng)有這個(gè)鍵for(Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if(e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;
addEntry(hash, key, value, i);return null;}
?
final int hash(Object k) {int h = 0h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4); }?
static int indexFor(int h, int length) {return h & (length-1);//等同于h%length }?
如果是第一個(gè)保存，先調(diào)用inflateTable方法給table分配空間：
private void inflateTable(int toSize) {//Find a power of 2 >= toSizeint capacity = roundUpToPowerOf2(toSize); //capacity的默認(rèn)值為16threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //默認(rèn)為12table = new Entry[capacity];} void addEntry(int hash, K key, V value, int bucketIndex) {if((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);} void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++; }
總結(jié)保存鍵值對(duì)過(guò)程：
1）計(jì)算鍵的哈希值
2）根據(jù)哈希值得到保存位置
3）插到對(duì)應(yīng)位置的鏈表頭部或更新已有值
4）根據(jù)需要擴(kuò)展table大小
例子：
Map<String,Integer> countMap = new HashMap<>(); countMap.put("hello", 1); countMap.put("world", 3); countMap.put("position", 4);?
?
?
3.查找方法
public V get(Object key) {if(key == null)return getForNullKey();Entry<K,V> entry = getEntry(key);return null == entry ? null : entry.getValue();}?
final Entry<K,V> getEntry(Object key) {if(size == 0) {return null;}//把key轉(zhuǎn)換位hash值int hash = (key == null) ? 0 : hash(key);//再把hash值換算為索引位置，快速查找for(Entry<K,V> e = table[indexFor(hash, table.length)];e != null; e = e.next) {Object k;if(e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}?
containsKey()方法邏輯與之類似：
public boolean containsKey(Object key) {return getEntry(key) != null; }HashMap可以方便高效地按鍵進(jìn)行操作，但如果要按值進(jìn)行操作，就要進(jìn)行遍歷：
public boolean containsValue(Object value) {if(value == null)return containsNullValue();Entry[] tab = table;for(int i = 0; i < tab.length ; i++)for(Entry e = tab[i] ; e != null ; e = e.next)if(value.equals(e.value))return true;return false;}4.按鍵刪除鍵值對(duì)
public V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);return(e == null ? null : e.value); } final Entry<K,V> removeEntryForKey(Object key) {if(size == 0) {return null;}int hash = (key == null) ? 0 : hash(key);int i = indexFor(hash, table.length);Entry<K,V> prev = table[i];Entry<K,V> e = prev;while(e != null) {Entry<K,V> next = e.next;Object k;if(e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++;size--;if(prev == e)table[i] = next;elseprev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e;}5.實(shí)現(xiàn)原理總結(jié)
1）根據(jù)鍵獲取和保存值的效率都很高，為O(1)，單向鏈表往往只有一個(gè)或
少數(shù)幾個(gè)節(jié)點(diǎn)，根據(jù)hash值就可以快速直接定位;
2）HashMap中的鍵值對(duì)沒(méi)有順序，因?yàn)閔ash值是隨機(jī)的。
注意，HashMap不是線程安全的，Java中還有一個(gè)類HashTable，它是Java最早實(shí)現(xiàn)的
容器類之一，實(shí)現(xiàn)了Map接口，實(shí)現(xiàn)原理與HashMap類似，但沒(méi)有特別優(yōu)化，它內(nèi)部通過(guò)
synchronized實(shí)現(xiàn)了線程安全。另外，在HashMap中鍵和值都可以為null，而在HashTable
中不可以。在不需要并發(fā)安全的場(chǎng)景中推薦使用HashMap。高并發(fā)場(chǎng)景中，推薦使用ConcurrentHashMap。
根據(jù)哈希值存取對(duì)象、比較對(duì)象是計(jì)算機(jī)程序中的一種重要思維方式，它使得存取對(duì)象主要依賴于自身
的哈希值，而不是與其他對(duì)象進(jìn)行比較，存取效率也與集合大小無(wú)關(guān)，高達(dá)O(1),即使是進(jìn)行比較，也能
比較Hash值提高比較效率。
二）HashSet
1.概述
HashSet實(shí)現(xiàn)了Set接口。
Set接口表示的是沒(méi)有重復(fù)元素，且不保證順序的容器的接口，它擴(kuò)展自Collection，
雖然沒(méi)有定義任何新方法，不過(guò)對(duì)于其中的一些方法，它有自己的規(guī)范。
public interface Set<E> extends Collection<E> {int size();boolean isEmpty();boolean contains(Object o);//迭代遍歷時(shí)不強(qiáng)制要求元素之間有特別的順序//但某些Set實(shí)現(xiàn)可能有順序，比如ThreeSetIterator<E> iterator();Object[] toArray();<T> T[] toArray(T[] a);//添加元素時(shí)，如果集合中已經(jīng)存在相同元素了，則不會(huì)改變集合，直接返回false//只有不存在時(shí)才會(huì)添加，返回trueboolean add(E e);boolean remove(Object o);boolean containsAll(Collection<?> c);//重復(fù)的元素不添加，不重復(fù)的元素才添加，如果集合有變化，返回trueboolean addAll(Collection<? extends E> c);boolean retainAll(Collection<?> c);boolean removeAll(Collection<?> c);void clear();boolean equals(Object o);int hashCode(); }構(gòu)造方法與HashMap類似：
public HashSet() public HashSet(int initialCapacity) public HashSet(int initialCapacity, float loadFactor) public HashSet(Collection<? extends E> c)與HashMap類似，HashSet要求元素重寫hashCode與equals方法，且對(duì)于兩個(gè)對(duì)象，
如果equals相同，則hashCode也必須相同。如果元素是自定義類特別要注意這一點(diǎn)。
public class Dog {private String name;private int number;public Dog(String name, int number) {this.name = name;this.number = number;}@Overridepublic String toString() {return "Name: " + name + " Number: " + number;} } Dog a = new Dog("King", 110);Dog b = new Dog("King", 110);HashSet<Dog> dogs = new HashSet<>();dogs.add(a);dogs.add(b);System.out.println("The set is " + dogs);//The set is [Name: King Number: 110, Name: King Number: 110]2.實(shí)現(xiàn)原理
HashSet內(nèi)部是用HashMap實(shí)現(xiàn)的，其內(nèi)部有一個(gè)HashMap實(shí)例變量：
private transient HashMap<E,Object> map;Map有鍵和值，HashSet相當(dāng)于只有鍵，值都是相同的固定值，這個(gè)值定義為：
private static final Object PRESENT = new Object();構(gòu)造方法：
public HashSet() {map = new HashMap<>();} public HashSet(int initialCapacity, float loadFactor) {map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(Collection<? extends E> c) {map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));addAll(c); }add方法：
public boolean add(E e) {return map.put(e, PRESENT)==null; }檢查是否包含：
public boolean contains(Object o) {return map.containsKey(o); }刪除：
public boolean remove(Object o) {return map.remove(o)==PRESENT; }迭代器：
public Iterator<E> iterator() {return map.keySet().iterator(); }3.HashSet特點(diǎn)總結(jié)
1）沒(méi)有重復(fù)元素
2）沒(méi)有順序
3）可以高效地添加，刪除，判斷元素是否存在
轉(zhuǎn)載于:https://www.cnblogs.com/Shadowplay/p/9969407.html
總結(jié)
以上是生活随笔為你收集整理的Java笔记（七）HashMap和HashSet的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： mysql常用的分组函数
- 下一篇： C# 程序执行时间差