HashMap簡介
HashMap 是一個散列表适室，它存儲的內(nèi)容是鍵值對(key-value)映射嚷兔。
HashMap 繼承于AbstractMap鸥拧，實現(xiàn)了Map茉稠、Cloneable、java.io.Serializable接口卿吐。
HashMap 的實現(xiàn)不是同步的，這意味著它不是線程安全的锋华。它的key、value都可以為null毯焕。此外衍腥，HashMap中的映射不是有序的磺樱。
HashMap 的實例有兩個參數(shù)影響其性能：“初始容量” 和 “加載因子”。容量 是哈希表中桶的數(shù)量婆咸，初始容量 只是哈希表在創(chuàng)建時的容量块差。加載因子 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時倔丈，則要對該哈希表進行 rehash 操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)）憨闰，從而哈希表將具有大約兩倍的桶數(shù)。
通常需五，默認加載因子是 0.75, 這是在時間和空間成本上尋求一種折衷鹉动。加載因子過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數(shù) HashMap 類的操作中宏邮，包括 get 和 put 操作泽示，都反映了這一點）。在設(shè)置初始容量時應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子蜜氨，以便最大限度地減少 rehash 操作次數(shù)械筛。如果初始容量大于最大條目數(shù)除以加載因子，則不會發(fā)生 rehash 操作记劝。
簡單版变姨，只實現(xiàn)put和get:
public class MyHashMap<K, V> {
private static int default_length = 16;
private MyEntry<K, V>[] entries;
public MyHashMap() {
super();
entries = new MyEntry[default_length];
}
public V put(K key, V value) {
int index = key.hashCode() % default_length;// hascode值除map大小取余
MyEntry<K, V> prevoius = entries[index];
for (MyEntry<K, V> entry = entries[index]; entry != null; entry = entry.next) {
if (entry.getKey().equals(key)) {
V oldValue = (V) entry.getValue();
entry.setValue(value);
return oldValue;
}
}
MyEntry<K, V> entry = new MyEntry<>(key, value);
entry.next = prevoius;
entries[index] = entry;
return null;
}
public K get(K key){
int index= key.hashCode()%default_length;
for (MyEntry<K,V> entry= entries[index];entry!=null;entry=entry.next){
if(entry.getKey().equals(key)){
return (K)entry.getValue();
}
}
return null;
}
private final class MyEntry<K, V> {
private K key;
private V value;
private MyEntry next;
public MyEntry() {
super();
}
public MyEntry(K key, V value) {
super();
this.key = key;
this.value = value;
}
public MyEntry(K key, V value, MyEntry next) {
super();
this.key = key;
this.value = value;
this.next = next;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public MyEntry getNext() {
return next;
}
public void setNext(MyEntry next) {
this.next = next;
}
}
}
復(fù)雜版：
public class MyHashMap {
//默認初始化大小 16
private static final int DEFAULT_INITIAL_CAPACITY = 16;
//默認負載因子 0.75
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
//臨界值
private int threshold;
//元素個數(shù)
private int size;
//擴容次數(shù)
private int resize;
private MyEntry[] table;
public MyHashMap() {
table = new MyEntry[DEFAULT_INITIAL_CAPACITY];
threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
size = 0;
}
private int index(Object key) {
//根據(jù)key的hashcode和entry長度取模計算key在entry中的位置
return key.hashCode() % table.length;
}
public void put(Object key, Object value) {
//key為null時需要特殊處理，為簡化實現(xiàn)忽略null值
if (key == null) return;
int index = index(key);
//遍歷index位置的entry厌丑，若找到重復(fù)key則更新對應(yīng)entry的值定欧，然后返回
MyEntry entry = table[index];
while (entry != null) {
if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {
entry.setValue(value);
return;
}
entry = entry.getNext();
}
//若index位置沒有entry或者未找到重復(fù)的key，則將新key添加到table的index位置
add(index, key, value);
}
private void add(int index, Object key, Object value) {
//將新的entry放到table的index位置第一個怒竿，若原來有值則以鏈表形式存放
MyEntry entry = new MyEntry(key, value, table[index]);
table[index] = entry;
//判斷size是否達到臨界值砍鸠，若已達到則進行擴容，將table的capacicy翻倍
if (size++ >= threshold) {
resize(table.length * 2);
}
}
private void resize(int capacity) {
if (capacity <= table.length) return;
MyEntry[] newTable = new MyEntry[capacity];
//遍歷原table耕驰，將每個entry都重新計算hash放入newTable中
for (int i = 0; i < table.length; i++) {
MyEntry old = table[i];
while (old!=null){
MyEntry next = old.getNext();
int index = index(old.getKey());
old.setNext(newTable[index]);
newTable[index] = old;
old=next;
}
}
//用newTable替table
table = newTable;
//修改臨界值
threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);
resize++;
}
public Object get(Object key){
//這里簡化處理爷辱，忽略null值
if (key == null) return null;
MyEntry entry= getEntry(key);
return entry == null ? null : entry.getValue();
}
public MyEntry getEntry(Object key){
MyEntry entry =table[index(key)];
while (entry!=null){
if (entry.getKey().hashCode()==key.hashCode()&&(entry.getKey()==key||entry.getKey().equals(key))){
return entry;
}
entry = entry.getNext();
}
return entry;
}
public void remove(Object key) {
if (key == null) return;
int index = index(key);
MyEntry pre = null;
MyEntry entry = table[index];
while (entry != null) {
if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {
if (pre == null) table[index] = entry.getNext();
else pre.setNext(entry.getNext());
//如果成功找到并刪除，修改size
size--;
return;
}
pre = entry;
entry = entry.getNext();
}
}
public boolean containsKey(Object key) {
if (key == null) return false;
return getEntry(key) != null;
}
public int size() {
return this.size;
}
public void clear() {
for (int i = 0; i < table.length; i++) {
table[i] = null;
}
this.size = 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("size:%s capacity:%s resize:%s\n\n", size, table.length, resize));
for (MyEntry entry : table) {
while (entry != null) {
sb.append(entry.getKey() + ":" + entry.getValue() + "\n");
entry = entry.getNext();
}
}
return sb.toString();
}
}
final class MyEntry {
private Object key;
private Object value;
private MyEntry next;
public MyEntry(Object key, Object value, MyEntry next) {
this.key = key;
this.value = value;
this.next = next;
}
public Object getKey() {
return key;
}
public void setKey(Object key) {
this.key = key;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public MyEntry getNext() {
return next;
}
public void setNext(MyEntry next) {
this.next = next;
}
}
