You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by mi...@apache.org on 2010/12/13 11:22:36 UTC
svn commit: r1045053 -
/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/fst/NodeHash.java
Author: mikemccand
Date: Mon Dec 13 10:22:35 2010
New Revision: 1045053
URL: http://svn.apache.org/viewvc?rev=1045053&view=rev
Log:
use more efficient quadratic hash impl; remove dead code
Modified:
lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/fst/NodeHash.java
Modified: lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/fst/NodeHash.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/fst/NodeHash.java?rev=1045053&r1=1045052&r2=1045053&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/fst/NodeHash.java (original)
+++ lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/fst/NodeHash.java Mon Dec 13 10:22:35 2010
@@ -28,8 +28,6 @@ final class NodeHash<T> {
private final FST<T> fst;
private final FST.Arc<T> scratchArc = new FST.Arc<T>();
- public static int conf;
-
public NodeHash(FST<T> fst) {
table = new int[16];
mask = 15;
@@ -113,10 +111,9 @@ final class NodeHash<T> {
public int add(Builder.UnCompiledNode<T> node) throws IOException {
// System.out.println("hash: add count=" + count + " vs " + table.length);
final int h = hash(node);
- int h2 = h;
- int c = 1;
+ int pos = h & mask;
+ int c = 0;
while(true) {
- final int pos = h2 & mask;
final int v = table[pos];
if (v == 0) {
// freeze & add
@@ -135,28 +132,22 @@ final class NodeHash<T> {
}
// quadratic probe
- h2 = h+(c + c*c)/2;
- c++;
- conf++;
+ pos = (pos + (++c)) & mask;
}
}
// called only by rehash
private void addNew(int address) throws IOException {
- final int h = hash(address);
- int h2 = h;
- int c = 1;
+ int pos = hash(address) & mask;
+ int c = 0;
while(true) {
- final int pos = h2 & mask;
if (table[pos] == 0) {
table[pos] = address;
break;
}
// quadratic probe
- h2 = h + (c + c*c)/2;
- c++;
- conf++;
+ pos = (pos + (++c)) & mask;
}
}