對(duì)于數(shù)據(jù)的搜索已有很多成熟的方案，比如Apace Lucene框架，結(jié)合ikanalyer等分詞器能實(shí)現(xiàn)很復(fù)雜和高效的搜索，或直接使用sql語(yǔ)言對(duì)數(shù)據(jù)庫(kù)關(guān)鍵字進(jìn)行搜索等。

但這些搜索都很重，對(duì)于已經(jīng)加載完成的數(shù)據(jù)列表并不適用。

比如有這樣一個(gè)需求：已經(jīng)加載了一個(gè)班的學(xué)生在一個(gè)List<Student>列表中，要根據(jù)學(xué)生和姓名和住址做一個(gè)模糊搜索。因?yàn)閿?shù)據(jù)已經(jīng)加載到List中，存在于內(nèi)存中，若再?gòu)臄?shù)據(jù)庫(kù)或網(wǎng)絡(luò)上去使用關(guān)鍵字取值并不是很優(yōu)的方案。而一般做法是在查找關(guān)鍵字里，遍歷整個(gè)列表逐個(gè)匹配，但若是如手機(jī)上做逐個(gè)輸入搜索的話會(huì)產(chǎn)生大量的循環(huán)操作，效率很低。

為此，今天分享一種比較對(duì)List列表比較高效的搜索方式。

思路：
1、傳入數(shù)據(jù)源List，并指定要搜索的字段；將這些字段的值拼接成一個(gè)字符串，并保存每個(gè)對(duì)象的值的起始和結(jié)束位置：
2、搜索時(shí)，先使用正則表達(dá)式在保存的搜索字符串找到位置，再利用這些位置在索引數(shù)據(jù)數(shù)組中找到對(duì)應(yīng)對(duì)象索引；

具體實(shí)現(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);
                // 將該字符串在總字符串中的起終位置保存下來,位置是索引值而非長(zhǎng)度
                int length = mKeyWordString.length();
                mIndexes[index] = length;
                mKeyWordString.append(searchKey);
                length = mKeyWordString.length();
                index++;
                // 保存新加搜索字段的索引值
                mIndexes[index] = (length > 0) ? length - 1 : 0;
                index++;
            }
        }
    }

    /**
     * 通過反射從對(duì)象中取出指定字段的值
     */
    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 返回搜索到的對(duì)象
     */
    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ù)組的下標(biāo)數(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ù)過多錯(cuò)誤
            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
     *            字符在整個(gè)字符串中的位置
     * @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;
    }

}

簡(jiǎn)單的使用和測(cè)試：

    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=天府大道四街]]

博客地址：對(duì)List對(duì)象列表屬性值的快速搜索