Java實現 - 如何提高散列表的速度

我正在實現一個散列表（按照要求）。它適用於小輸入，但不幸的是，處理大量輸入時速度太慢。我試過BufferedInputStream，但沒有任何區別。基本上我按照下面的邏輯實現它。任何想法如何提高速度？是否有導致性能不佳的特定功能？或者我們可能需要關閉掃描儀？Java實現 - 如何提高散列表的速度

int [] table = new int [30000];// creat an array as the table 
Scanner scan = new Scanner (System.in); //use scanner to read the input file. 
while (scan.hasNextLine()) { 
     //read one line at a time, and a sequence of int into an array list called keys 
     // functions used here is string.split(" "); 
} 
hashFuction{ 
     //use middle-squaring on each elements to the array list keys. 
     // Math.pow() and % 30000, which is the table size, to generate the hash value 
     // assign table [hashvalue]= value 
}

來源

2014-09-26 stillAFanOfTheSimpsons

您至少需要弄清楚I/O是瓶頸還是散列表。如果你使用'HashMap'而不是你的類，你的程序如何執行？如果它是你的散列表，我們需要看它的代碼。 – 2014-09-26 04:51:50

謝謝。你能推薦一種檢查程序的哪一部分是瓶頸的方法嗎？ – stillAFanOfTheSimpsons 2014-09-26 05:14:55

重寫代碼以使用'HashMap'並查看它運行的速度。如果速度很快，那麼問題必須存在於散列表類中。如果它仍然很慢，那麼問題就在課外。 – 2014-09-26 05:20:40

所以首先，你現在應該知道程序的哪個部分很慢。優化一切是一個愚蠢的想法，優化快速部分更糟糕。

Math.pow（）和30000％，這是該表的大小

這是非常錯誤的。

從不使用浮點運算來處理哈希等問題。它速度很慢，分佈不均勻。
切勿使用既不是兩個冪也不是冪的表格大小。

您沒有告訴我們關於什麼是哈希以及爲什麼......因此我們假設您需要將一對兩個整數映射到表中。

class IntPair { 
    private int x; 
    private int y; 

    public int hashCode() { 
     // the multiplier must be odd for good results 
     // its exact value doesn't matter much, but it mustn't equal to your table size; ideally, it should be co-prime 
     return 54321 * x + y; 
    } 

    public boolean equals() { 
     do yourself 
    } 
} 

//// Prime table size. The division is slow, but it works slightly better than power of two. 

int[] table = new int[30011]; // this is a prime 

int hashCodeToIndex(int hashCode) { 
    int nonNegative = hashCode & Integer.MAX_VALUE; 
    return nonNegative % table.length; 
} 

//// Power of two table size. No division, faster. 

int[] table2 = new int[1<<15]; // this is 2**15, i.e., 32768 

int smear(int hashCode) { 
    // doing nothing may be good enough, if the hashCode is well distributed 
    // otherwise, see e.g., https://github.com/google/guava/blob/c234ed7f015dc90d0380558e663f57c5c445a288/guava/src/com/google/common/collect/Hashing.java#L46 
    return hashCode; 
} 

int hashCodeToIndex(int hashCode) { 
    // the "&" cleans all unwanted bits 
    return smear(hashCode) & (table2.length - 1); 
} 

// an alternative, explanation upon request 
int hashCodeToIndex2(int hashCode) { 
    return smear(hashCode) >>> 17; 
}

來源

2014-09-26 05:02:33 maaartinus

+1使用浮點必須是壞的，但它不必要的複雜，Math.pow速度很慢。如果hashCode不完美，使用＆是最快的，但是沒有很好的分佈。它適用於低負載因素。 – 2014-09-26 06:03:33

Java實現 - 如何提高散列表的速度

回答

相關問題