Как создать структуру данных для поиска значений в таблице?

Структуры данных для поиска в таблице

Когда нужно искать значения в таблице данных, выбор подходящей структуры зависит от типа данных, частоты поисков и требований к памяти. Рассмотрим основные подходы и их реализации.

1. HashMap для быстрого поиска по уникальному ключу

Это наиболее эффективное решение, когда нужен поиск по первичному ключу за O(1):

class Table<K, V> {
    private Map<K, V> index = new HashMap<>();
    
    public void insert(K key, V value) {
        index.put(key, value);
    }
    
    public V findByKey(K key) {
        return index.get(key);
    }
    
    public boolean exists(K key) {
        return index.containsKey(key);
    }
}

2. B-Tree для больших наборов данных

B-Tree идеален для больших таблиц с гарантированной сортировкой и поиском по диапазону:

class BTreeNode {
    List<Integer> keys = new ArrayList<>();
    List<BTreeNode> children = new ArrayList<>();
    boolean isLeaf = true;
}

class BTree {
    private BTreeNode root;
    private int order = 3;
    
    public BTreeNode search(BTreeNode node, int key) {
        int i = 0;
        while (i < node.keys.size() && key > node.keys.get(i)) {
            i++;
        }
        
        if (i < node.keys.size() && key == node.keys.get(i)) {
            return node;
        }
        
        if (node.isLeaf) {
            return null;
        }
        
        return search(node.children.get(i), key);
    }
}

3. Inverted Index для полнотекстового поиска

Используется для индексирования — отображает какие документы содержат каждый термин:

class InvertedIndex {
    private Map<String, Set<Integer>> index = new HashMap<>();
    
    public void addDocument(int docId, String text) {
        String[] terms = text.toLowerCase().split(" ");
        for (String term : terms) {
            index.computeIfAbsent(term, k -> new HashSet<>())
                 .add(docId);
        }
    }
    
    public Set<Integer> search(String term) {
        return index.getOrDefault(term, new HashSet<>());
    }
}

4. Secondary Index для поиска по не-уникальным полям

Позволяет быстро найти все записи с определённым значением:

class SecondaryIndex<K, V> {
    private Map<K, List<V>> index = new HashMap<>();
    
    public void add(K key, V value) {
        index.computeIfAbsent(key, k -> new ArrayList<>())
             .add(value);
    }
    
    public List<V> find(K key) {
        return index.getOrDefault(key, new ArrayList<>());
    }
}

5. Trie для поиска с префиксом

Отлично подходит для автодополнения и поиска по частичному совпадению:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
    Object value;
}

class Trie {
    private TrieNode root = new TrieNode();
    
    public void insert(String key, Object value) {
        TrieNode node = root;
        for (char ch : key.toCharArray()) {
            node = node.children.computeIfAbsent(ch, k -> new TrieNode());
        }
        node.isEndOfWord = true;
        node.value = value;
    }
}

Сравнение сложности

HashMap: O(1) поиск, идеален для уникальных ключей TreeMap: O(log n) поиск, сортированные данные B-Tree: O(log n) поиск, большие наборы данных Inverted Index: O(m) поиск, полнотекстовый поиск Trie: O(m) поиск, префиксный поиск

Выбор структуры

HashMap — если нужен поиск за O(1) по уникальному ключу TreeMap — если нужна сортировка и поиск диапазона B-Tree — если много данных на диске Inverted Index — для полнотекстового поиска Trie — для автодополнения и префиксного поиска

Выбор должен базироваться на требованиях задачи: частотность поисков, размер данных и тип запросов.