Lucene中运用的hash算法
Lucene中使用的hash算法
最近一直在研究Lucene的源码,其中有许多设计到hash算法的地方。于是自己整理一下,以加深自己的理解。这只是我个人的理解。如果有不对的地方。希望大家勇于拍砖。
TermsHashPerField.java中有一个hash算法:
final char[] tokenText = termAtt.buffer();
final int tokenTextLen = termAtt.length();
// Compute hashcode & replace any invalid UTF16 sequences
int downto = tokenTextLen;
int code = 0;
while (downto > 0) {
char ch = tokenText[--downto];
if (ch >= UnicodeUtil.UNI_SUR_LOW_START && ch <= UnicodeUtil.UNI_SUR_LOW_END) {
if (0 == downto) {
// Unpaired
ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
} else {
final char ch2 = tokenText[downto-1];
if (ch2 >= UnicodeUtil.UNI_SUR_HIGH_START && ch2 <= UnicodeUtil.UNI_SUR_HIGH_END) {
// OK: high followed by low. This is a valid
// surrogate pair.
code = ((code*31) + ch)*31+ch2;
downto--;
continue;
} else {
// Unpaired
ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
}
}
} else if (ch >= UnicodeUtil.UNI_SUR_HIGH_START && (ch <= UnicodeUtil.UNI_SUR_HIGH_END ||
ch == 0xffff)) {
// Unpaired or 0xffff
ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
}
code = (code*31) + ch;
}
int hashPos = code & postingsHashMask;
代码最后的hashPos是最终的hash值。如果仔细看一下的话,你就会发现上面代码的hash算法是不是非常的眼熟!
好好回忆一下自己是否见过,想起来了吧。是不是跟java自带的源码中的String的hashcode算法相似呢。呵呵。是否想起来了呢?如果没有,请赶紧温习一下java源码吧。呵呵。
最近一直在研究Lucene的源码,其中有许多设计到hash算法的地方。于是自己整理一下,以加深自己的理解。这只是我个人的理解。如果有不对的地方。希望大家勇于拍砖。
TermsHashPerField.java中有一个hash算法:
final char[] tokenText = termAtt.buffer();
final int tokenTextLen = termAtt.length();
// Compute hashcode & replace any invalid UTF16 sequences
int downto = tokenTextLen;
int code = 0;
while (downto > 0) {
char ch = tokenText[--downto];
if (ch >= UnicodeUtil.UNI_SUR_LOW_START && ch <= UnicodeUtil.UNI_SUR_LOW_END) {
if (0 == downto) {
// Unpaired
ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
} else {
final char ch2 = tokenText[downto-1];
if (ch2 >= UnicodeUtil.UNI_SUR_HIGH_START && ch2 <= UnicodeUtil.UNI_SUR_HIGH_END) {
// OK: high followed by low. This is a valid
// surrogate pair.
code = ((code*31) + ch)*31+ch2;
downto--;
continue;
} else {
// Unpaired
ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
}
}
} else if (ch >= UnicodeUtil.UNI_SUR_HIGH_START && (ch <= UnicodeUtil.UNI_SUR_HIGH_END ||
ch == 0xffff)) {
// Unpaired or 0xffff
ch = tokenText[downto] = UnicodeUtil.UNI_REPLACEMENT_CHAR;
}
code = (code*31) + ch;
}
int hashPos = code & postingsHashMask;
代码最后的hashPos是最终的hash值。如果仔细看一下的话,你就会发现上面代码的hash算法是不是非常的眼熟!
好好回忆一下自己是否见过,想起来了吧。是不是跟java自带的源码中的String的hashcode算法相似呢。呵呵。是否想起来了呢?如果没有,请赶紧温习一下java源码吧。呵呵。