HashMap (Открытая адресация) Реализация ОЧЕНЬ медленная - PullRequest
Новая
       15

HashMap (Открытая адресация) Реализация ОЧЕНЬ медленная

2 голосов
/ 02 декабря 2019

По какой-то причине моя реализация 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;
  }
}

1 Ответ

2 голосов
/ 02 декабря 2019

Похоже, что в этой части есть проблема: 

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

Поскольку numKeys и size оба являются целыми числами, это целочисленное деление - т.е. оно округляется в меньшую сторону. Таким образом, результат деления будет больше, чем loadFactor только тогда, когда numKeys и size равны, что фактически означает, что ваш класс ведет себя как хеш-таблица с коэффициентом загрузки 1, а не 0,5. Это приводит к тому, что ваша схема открытой адресации ухудшается до сложности O (n) вместо O (1).

Решение состоит в том, чтобы изменить это условие, чтобы оно выполняло сравнение правильно. Во-первых, будьте осторожны, когда делите целые числа, но вы хотите, чтобы ответ был двойным;Вы должны разыграть удвоение перед делением. Во-вторых, не используйте Double.compare, если вместо этого вы можете использовать < или >. Фиксированная версия выглядит следующим образом: 

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

Или, чтобы полностью избежать разделения, вы можете эквивалентно проверить, если numKeys > loadFactor * size.

...