對于數(shù)據(jù)的搜索已有很多成熟的方案楣黍，比如Apace Lucene框架，結(jié)合ikanalyer等分詞器能實現(xiàn)很復(fù)雜和高效的搜索，或直接使用sql語言對數(shù)據(jù)庫關(guān)鍵字進行搜索等。
但這些搜索都很重谍咆，對于已經(jīng)加載完成的數(shù)據(jù)列表并不適用。
比如有這樣一個需求：已經(jīng)加載了一個班的學(xué)生在一個List<Student>列表中香罐，要根據(jù)學(xué)生和姓名和住址做一個模糊搜索卧波。因為數(shù)據(jù)已經(jīng)加載到List中，存在于內(nèi)存中庇茫，若再從數(shù)據(jù)庫或網(wǎng)絡(luò)上去使用關(guān)鍵字取值并不是很優(yōu)的方案港粱。而一般做法是在查找關(guān)鍵字里，遍歷整個列表逐個匹配旦签，但若是如手機上做逐個輸入搜索的話會產(chǎn)生大量的循環(huán)操作查坪，效率很低。
為此宁炫，今天分享一種比較對List列表比較高效的搜索方式偿曙。
思路：
1、傳入數(shù)據(jù)源List羔巢，并指定要搜索的字段望忆；將這些字段的值拼接成一個字符串罩阵，并保存每個對象的值的起始和結(jié)束位置：
2、搜索時启摄，先使用正則表達式在保存的搜索字符串找到位置稿壁，再利用這些位置在索引數(shù)據(jù)數(shù)組中找到對應(yīng)對象索引；
具體實現(xiàn)：
package com.fansion;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class FSearchTool {
private StringBuffer mKeyWordString = new StringBuffer();
private List<Object> mSearchObjs = new ArrayList<>();
private int[] mIndexes;
public FSearchTool(List<? extends Object> objects, String... fields) throws Exception {
super();
init(objects, fields);
}
private void init(List<? extends Object> objs, String... fields) throws Exception {
if (objs != null) {
mKeyWordString.setLength(0);
mSearchObjs.clear();
mSearchObjs = new ArrayList<>(objs);
mIndexes = new int[mSearchObjs.size() * 2];
int index = 0;
for (int i = 0; i < mSearchObjs.size(); i++) {
Object info = mSearchObjs.get(i);
// 指定要搜索的字段
String searchKey = getSearchKey(info, fields);
// 將該字符串在總字符串中的起終位置保存下來,位置是索引值而非長度
int length = mKeyWordString.length();
mIndexes[index] = length;
mKeyWordString.append(searchKey);
length = mKeyWordString.length();
index++;
// 保存新加搜索字段的索引值
mIndexes[index] = (length > 0) ? length - 1 : 0;
index++;
}
}
}
/**
* 通過反射從對象中取出指定字段的值
*/
private String getSearchKey(Object obj, String... fields) throws Exception {
StringBuilder searchKeys = new StringBuilder();
Class<? extends Object> clazz = obj.getClass();
try {
for (String str : fields) {
// 搜索字段使用空格隔開
Field f = clazz.getDeclaredField(str);
f.setAccessible(true);
Object val = f.get(obj);
searchKeys.append(val).append(" ");
f.setAccessible(false);
}
} catch (Exception e) {
throw new Exception("取值異常：" + e.getMessage());
}
return searchKeys.toString();
}
/**
* 搜索結(jié)果
*
* @param keyWords
* 搜索的關(guān)鍵字歉备，要去掉首尾的空格
* @return 返回搜索到的對象
*/
public List<Object> searchTasks(String keyWords) {
List<Object> searchedTask = new ArrayList<>();
int[] searchIndex = getSearchIndex(keyWords);
for (int index : searchIndex) {
if (index != -1 && index < mSearchObjs.size() * 2) {
Object info = mSearchObjs.get(index / 2);
if (info != null && !searchedTask.contains(info)) {
searchedTask.add(info);
}
}
}
return searchedTask;
}
/**
* 找到匹配的索引數(shù)據(jù)
*
* @param keyWords
* 搜索的關(guān)鍵字
* @return 在初始化的索引數(shù)組的下標數(shù)組
*/
private int[] getSearchIndex(String keyWords) {
Pattern pattern = Pattern.compile(keyWords, Pattern.CASE_INSENSITIVE | Pattern.LITERAL);
Matcher matcher = pattern.matcher(mKeyWordString.toString());
ArrayList<Integer> searchResult = new ArrayList<>();
while (matcher.find()) {
// 不宜在此處再做循環(huán)傅是，否則可能造成循環(huán)次數(shù)過多錯誤
searchResult.add(matcher.start());
}
int[] searchIndexes = new int[searchResult.size()];
for (int i = 0; i < searchIndexes.length; i++) {
int findIndex = findIndex(searchResult.get(i));
searchIndexes[i] = (findIndex / 2) * 2;
}
return searchIndexes;
}
/**
* 使用二分法找到指定字符位置在索引數(shù)組中的位置
*
* @param charAt
* 字符在整個字符串中的位置
* @return 在索引數(shù)組中的位置
*/
private int findIndex(int charAt) {
int low = 0;
int high = mIndexes.length - 1;
int mid = -1;
while (low <= high) {
mid = (low + high) >>> 1;
int midVal = mIndexes[mid];
if (midVal < charAt) {
low = mid + 1;
} else if (midVal > charAt) {
high = mid - 1;
} else {
return mid;
}
}
return mid;
}
}
簡單的使用和測試：
public static void main(String[] args) {
List<Student> students = new ArrayList<>();
students.add(new Student("001", "小王", "天府大道一街"));
students.add(new Student("002", "小王", "天府大道二街"));
students.add(new Student("003", "小紅", "天府大道三街"));
students.add(new Student("004", "小明", "天府大道四街"));
students.add(new Student("005", "小王", "天府大道五街"));
students.add(new Student("006", "小王", "軟件園南門"));
students.add(new Student("007", "小張", "吉泰路"));
try {
FSearchTool tool = new FSearchTool(students, "name", "address");
System.out.println(tool.searchTasks("明"));
} catch (Exception e) {
e.printStackTrace();
}
}
輸出結(jié)果：
[Student [id=004, name=小明, address=天府大道四街]]
博客地址：對List對象列表屬性值的快速搜索
