java - HashMap(开放寻址)实现非常慢

Question

出于某种原因，我使用开放寻址的 HashMap 实现在处理大数据集时运行非常缓慢，但我无法确切地找出原因。任何人都可以提供一些见解吗？我只是一个数据结构学生，试图弄清楚为什么我的数据结构如此低效。

我在较小的数据集上运行它，它在我期望的时间内工作，但是一旦我增加它，它就会在我身上失败。

import java.util.ArrayList;
import java.util.List;
import java.lang.Math;
import java.util.Collections;
import java.lang.reflect.Array;
/**
 * @author Cameron Berger
 * HASHMap if a data structure which is suppose to be faster than an AVL tree
 * for set() and get(), however, I was unsucessful in this. But it works!
 */
public class HASHMap<K extends Comparable<K>,V> implements Map<K,V>{
  private class Node{
    public K k;
    public V val;

    public Node(K key, V value) {
      k      = key;
      val    = value;
    }
  }

  //time to implement
  private List<Node> arr;
  private int numKeys;
  private int size;
  private double loadFactor = 0.5;
  /**
   * Constructor for HASHMap
   **/
  public HASHMap(){
    size = 16;
    arr = new ArrayList<Node>(Collections.nCopies(size, null));
    numKeys = 0;
  }

  public V get(K key){
    int index = Math.abs(key.hashCode())%size;
    Node n;
    for(int i=index; ; i=(i+1)%size){
      n = arr.get(i);
      if (n == null)
        return null;
      else if(key.compareTo(n.k)==0)
        return n.val;
    }
  }

  public void set(K key, V value){
    int index = Math.abs(key.hashCode())%size;
    Node n;
    for(int i=index; ; i=(i+1)%size){
      n = arr.get(i);
      if (n == null){
        Node temp = new Node(key, value);
        arr.set(i, temp);
        numKeys++;
        break;
      }
    }
    if(Double.compare((numKeys/size),loadFactor)>0){
      this.reinitialize();
    }
  }
  /**
   * reinitialize reinitializes the HashMap if the loadFactor condition is met
   * or there is too much spill over
   **/
  private void reinitialize(){
    int nsize = size*2;
    List<Node> nArr = new ArrayList<Node>(Collections.nCopies(nsize, null));
    Node temp;

    for(int i=0; i<size; i++){
      temp = arr.get(i);
      if(temp!=null){
        K key = temp.k;
        int index = Math.abs(key.hashCode())%nsize;
        for(int j=index; ; j=(j+1)%nsize){
          Node n = nArr.get(j);
          if(n==null){
            nArr.set(j, temp);
            break;
          }
        }
      }
    }
    this.size = nsize;
    this.arr = nArr;
  }

  public int size(){ return numKeys; }

  public List<K> keys(){
    List<K> keylist = new ArrayList<K>();
    for(int i=0; i<size; i++){
      Node n = arr.get(i);
      if(n!=null)
        keylist.add(n.k);
    }
    return keylist;
  }

  public List<V> values(){
    List<V> valuelist = new ArrayList<V>();
    for(int i=0; i<size; i++){
      Node n = arr.get(i);
      if(n!=null)
        valuelist.add(n.val);
    }
    return valuelist;
  }
}

Answer 1

貌似这部分有问题:

    if(Double.compare((numKeys/size),loadFactor)>0){
      this.reinitialize();
    }

自 numKeys和 size都是整数，这是整数除法 - 即它向下舍入。所以除法的结果只会大于 loadFactor当 numKeys和 size是相等的，这实际上意味着您的类的行为类似于负载因子为 1 而不是 0.5 的哈希表。这会导致您的开放寻址方案恶化为 O(n) 复杂度而不是 O(1)。

解决方案是更改此条件，以便正确进行比较。首先，当你除以整数但你希望答案是 double 时要小心；你需要在分割前加倍。二、不要用 Double.compare什么时候可以使用 <或 >反而。固定版本如下所示:

    if((double) numKeys / size > loadFactor) {
        this.reinitialize();
    }

或者，为了完全避免除法，您可以等效地测试是否 numKeys > loadFactor * size .