HashMap的實現在java中如何更快更好

Question

我有HashMap的實現，但是對我來說操作太慢了，它必須像正常的hashmap一樣快。 這是代碼：

package Map; 
public class HashMap<K, V> { 

private Entry<K, V>[] table; // Array of Entry. 
private int capacity = 4; // Initial capacity of HashMap 

static class Entry<K, V> { 
    K key; 
    V value; 
    Entry<K, V> next; 

    public Entry(K key, V value, Entry<K, V> next) { 
     this.key = key; 
     this.value = value; 
     this.next = next; 
    } 
} 

@SuppressWarnings("unchecked") 
public HashMap() { 
    table = new Entry[capacity]; 
} 

/** 
* Method allows you put key-value pair in HashMapCustom. If the map already 
* contains a mapping for the key, the old value is replaced. Note: method 
* does not allows you to put null key though it allows null values. 
* Implementation allows you to put custom objects as a key as well. Key 
* Features: implementation provides you with following features:- >provide 
* complete functionality how to override equals method. >provide complete 
* functionality how to override hashCode method. 
* 
* @param newKey 
* @param data 
*/ 
public void put(K newKey, V data) { 
    if (newKey == null) 
     return; // does not allow to store null. 

    // calculate hash of key. 
    int hash = hash(newKey); 
    // create new entry. 
    Entry<K, V> newEntry = new Entry<K, V>(newKey, data, null); 

    // if table location does not contain any entry, store entry there. 
    if (table[hash] == null) { 
     table[hash] = newEntry; 
    } else { 
     Entry<K, V> previous = null; 
     Entry<K, V> current = table[hash]; 

     while (current != null) { // we have reached last entry of bucket. 
      if (current.key.equals(newKey)) { 
       if (previous == null) { // node has to be insert on first of 
             // bucket. 
        newEntry.next = current.next; 
        table[hash] = newEntry; 
        return; 
       } else { 
        newEntry.next = current.next; 
        previous.next = newEntry; 
        return; 
       } 
      } 
      previous = current; 
      current = current.next; 
     } 
     previous.next = newEntry; 
    } 
} 

/** 
* Method returns value corresponding to key. 
* 
* @param key 
*/ 
public V get(K key) { 
    int hash = hash(key); 
    if (table[hash] == null) { 
     return null; 
    } else { 
     Entry<K, V> temp = table[hash]; 
     while (temp != null) { 
      if (temp.key.equals(key)) 
       return temp.value; 
      temp = temp.next; // return value corresponding to key. 
     } 
     return null; // returns null if key is not found. 
    } 
} 

public boolean containsKey(K key) { 
    int hash = hash(key); 
    if (table[hash] == null) { 
     return false; 
    } else { 
     Entry<K, V> temp = table[hash]; 
     while (temp != null) { 
      if (temp.key.equals(key)) 
       return true; 
      temp = temp.next; // return value corresponding to key. 
     } 
    } 
    return false; 
} 

/** 
* Method removes key-value pair from HashMapCustom. 
* 
* @param key 
*/ 
public boolean remove(K deleteKey) { 

    int hash = hash(deleteKey); 

    if (table[hash] == null) { 
     return false; 
    } else { 
     Entry<K, V> previous = null; 
     Entry<K, V> current = table[hash]; 

     while (current != null) { // we have reached last entry node of 
            // bucket. 
      if (current.key.equals(deleteKey)) { 
       if (previous == null) { // delete first entry node. 
        table[hash] = table[hash].next; 
        return true; 
       } else { 
        previous.next = current.next; 
        return true; 
       } 
      } 
      previous = current; 
      current = current.next; 
     } 
     return false; 
    } 

} 

/** 
* Method displays all key-value pairs present in HashMapCustom., insertion 
* order is not guaranteed, for maintaining insertion order refer 
* LinkedHashMapCustom. 
* 
* @param key 
*/ 
public void display() { 

    for (int i = 0; i < capacity; i++) { 
     if (table[i] != null) { 
      Entry<K, V> entry = table[i]; 
      while (entry != null) { 
       System.out.print("{" + entry.key + "=" + entry.value + "}" + " "); 
       entry = entry.next; 
      } 
     } 
    } 

} 

/** 
* Method implements hashing functionality, which helps in finding the 
* appropriate bucket location to store our data. This is very important 
* method, as performance of HashMapCustom is very much dependent on this 
* method's implementation. 
* 
* @param key 
*/ 
private int hash(K key) { 
    return Math.abs(key.hashCode()) % capacity; 
} 

} 

，當我嘗試把大數據，如：

HashMap<Integer,String> map = new HashMap(); 
long startTime = System.currentTimeMillis(); 
for(int i = 0 ; i < 200000000; i++){ 
map.put(i, "kotek"+i); 
} 
System.out.println(System.currentTimeMillis() - startTime); 

它要花很長的時間。我必須在沒有其他集合的情況下實現它：Set等。我必須像普通的hashMap那樣快速地放置，移除，獲取和包含關鍵字，但我不知道如何實現該快速地圖。

Answer 1

你的地圖很慢的原因是你有很多衝突。你的容量是4，你永遠不會擴大它。因此，在4個第一個put()調用後，操作變得近似O（N）。同樣如William所說，你在桶的末尾添加新的條目。因此，將其作爲第一個元素進行添加將會提升性能。但它仍然不是一個很好的做法，讓您的地圖在4大小不變 - 因爲你的put()將被罰款，但get()仍將是O（N）

編輯 你不能預先考慮項。既然你必須查看桶上的所有條目，以確保你沒有等於鍵