해시 테이블의 충돌 해결

Question

해시 작업 방법을 더 잘 이해하기 위해 Java에서 해시 테이블을 직접 구현하려고 시도하고 있습니다. 나는 별도의 체인을 사용하고 테이블을 성장시키고로드가 75 % 이상이되거나 길이가 20을 초과하는 단일 체인을 가질 때 모든 것을 다시 채찍질합니다. 나는 문자열을 해시합니다. 내가 생각할 수있는 모든 것을 시도했지만 테이블을 만들려고 할 때 몇 초 동안 실행 한 다음 grow 메소드에서 StackOverflowError를 발생시킵니다.

실제 HashTable에 대한 코드입니다. 여기에는 실제 테이블에 대한 arrayList와 가장 긴 체인의 개수 및 크기를 추적하는 int가 포함됩니다. 또한 삽입, 증가 (새로운 arrayList에있는 모든 것을 재 해석), 문자열 해시 및 getter/setters뿐만 아니라 주어진 수보다 높은 소수를 찾는 메소드도 포함됩니다. 여기

import java.util.ArrayList; 
import java.util.LinkedList; 

public class HashTable { 
    private ArrayList<LinkedList<String>> hashes; 
    private int collisionCounter; //the total amount of collisions that have occurred 
    private int longest; //the length collision 
    private int size; 

    public HashTable(int size) { 
     this.hashes = new ArrayList<LinkedList<String>>(); 
     for (int i = 0; i < size; i++) { 
      hashes.add(new LinkedList<String>()); 
     } 
     this.collisionCounter = 0; 
     this.longest = 0; 
     this.size = size; 
    } 

    public int getCollisionCounter() { 
     return collisionCounter; 
    } 

    public int size() { 
     return this.size; 
    } 

    public int getLongest() { 
     return this.longest; 
    } 

    //grows array to a new size 
    public void grow(int newSize, int numElements) { 
     ArrayList<LinkedList<String>> oldHashes = new ArrayList<LinkedList<String>>(this.hashes); 
     this.hashes = new ArrayList<LinkedList<String>>(); 
     this.collisionCounter = 0; 
     this.longest = 0; 
     this.size = newSize; 
     for (int i = 0; i < this.size; i++) { 
      hashes.add(new LinkedList<String>()); 
     } 
     for (int i = 0; i < oldHashes.size(); i++) { 
      LinkedList<String> currentList = oldHashes.get(i); 
      for (int q = 0; q < currentList.size(); q++) { 
       this.insert(currentList.get(q)); 
      } 
     } 
     if (this.longest > 20 || this.load(numElements) > .75) { 
      newSize = newSize + 20; 
      newSize = this.findPrime(newSize); 
      this.grow(newSize, numElements); 
     } 

    } 

    //inserts into hashtable keeps track of collisions and the longest chain 
    public void insert(String element) { 
     int index = this.hash(element); 
     this.hashes.get(index).add(element); 
     if (index < this.size) { 
      if (this.hashes.get(index).size() > 1) { 
       this.collisionCounter++; 
       if (this.hashes.size() > this.longest) { 
        this.longest++; 
       } 
      } 
     } 

    } 

    //finds the first prime number that is larger that the starting number or the original number if that is prime 
    //if used to find a new table size the int in the parameters will need to be incremented 
    public int findPrime(int startInt) { 
     int newNum = startInt++; 
     boolean isFound = false; 
     while (!isFound) { 
      boolean isPrime = true; 
      int divisor = 2; 
      while (isPrime && divisor < newNum/2) { 
       if (newNum % divisor == 0) { 
        isPrime = false; 
       } else { 
        divisor++; 
       } 
      } 
      if (isPrime) { 
       isFound = true; 
      } else { 
       newNum++; 
      } 
     } 
     return newNum; 
    } 

    public double load(int numElements) { 
     return (numElements + 0.0)/(this.size + 0.0); //int division may be a problem 
    } 

    //helper method for insert and search creates hash value for a word 
    public int hash(String ele) { 
     char[] chars = ele.toCharArray(); 
     double hashCode = 0; 
     for (int i = 0; i < chars.length; i++) { 
      hashCode += chars[i] * Math.pow(5521, chars.length - i); 
     } 
     if (hashCode < 0) { 
      hashCode = hashCode + this.size; 
     } 
     return (int) (hashCode % this.size); 
    } 

    //method to search for a word in hashtable finds a string in the hastable return true if found false if not found 
    public boolean search(String goal) { 
     int index = this.hash(goal); 
     LinkedList<String> goalList = this.hashes.get(index); 
     for (int i = 0; i < goalList.size(); i++) { 
      if (goalList.get(i).equals(goal)) { 
       return true; 
      } 
     } 
     return false; 
    } 
} 

(이것은 간다로 해싱) 실제로 모든 단어의 ArrayList를 소요 어레이에 삽입 테이블 구축 방법에 대한 코드와로드/충돌 길이를 확인하고 성장 필요한 경우.

public static HashTable createHash(ArrayList<String> words) { 
     int initSize = findPrime(words.size()); 
     HashTable newHash = new HashTable(initSize); 
     for (int i = 0; i < words.size(); i++) { 
      newHash.insert(words.get(i)); 

      if (newHash.load(i) > .75 || newHash.getLongest() > 20) { 
       int size = newHash.size(); 
       size = size + 25; 
       int newSize = findPrime(size); 
       newHash.grow(newSize, i); 
      } 
     } 
     return newHash; 
    } 

죄송이를 통해 정렬하는 코드를 많이하지만 난 내가 잘못 여기서 뭐하는 거지 알아낼 수 없습니다 그것을 아래로 응축 할 수있는 방법을 모른다. 어떤 도움이라도 정말 고맙습니다! 당신의 insert 방법에서

Answer 1

당신이 그것을 몇 초 동안 실행 한 후 StackOverflowError 안타 이유를 설명 긴 체인

if(this.hashes.get(index).size() > this.longest) { 
    this.longest = this.hashes.get(index).size(); 
} 

를 추적하는 대신 다음이 있어야합니다, 당신은 값 때문에 무한 재귀된다 this.hashes.size()은 변경되지 않으므로 longest은 변경되지 않습니다.