Java 具有字符串键部分重用的内存映射

Question

我一张地图有几万条记录。映射键是 s3://mybucket/some/path/2021/03/03/file.txt、s3://mybucket/some/path/2021/03/04/file.txt 等字符串，值是 0 或 1。目前我用的是HashMap，但是内存占用太高，想降低。

我正在寻找一个键值对并利用关键部分可重用性的东西。自然而然想到的是用一些树结构来存储前缀。

有人可以指出一个合适的实现，最好是轻量级的吗？

Answer 1

Prefix Tree 是一种可能的解决方案，在 space 复杂性方面将是轻量级的。这是使用 Trie 对 Prefix Tree 的 Java 实现。我对 child 使用了 HashMap，因为我不确定字母表的大小。如果您确定字典中的字母表大小，则绝对可以为 child TrieNode 使用固定长度。只有当 TrieNode 标记字符串结束时，每个 TrieNode 才会存储密钥的 value。当您找到存储密钥最后一个 character 的 TrieNode 时，您就可以访问 value;

class TrieNode {
    HashMap<Character, TrieNode> child;
    boolean isEnd;
    int value;

    TrieNode() {
        this.child = new HashMap<>();
    }

}

public class PrefixTree {
    private TrieNode root;

    public PrefixTree() {
        this.root = new TrieNode();
    }

    public void put(String key, int value) {
        char[] data = key.toCharArray();
        TrieNode tempNode = root;

        for (char ch : data) {
            if (tempNode.child.get(ch) == null) {
                tempNode.child.put(ch, new TrieNode());
            }
            tempNode = tempNode.child.get(ch);

        }
        tempNode.isEnd = true;
        tempNode.value = value;
    }


    public TrieNode get(String key) {
        char[] data = key.toCharArray();
        TrieNode tempNode = root;
        for (char ch : data) {
            if (tempNode.child.get(ch) == null) {
                return null;
            }
            tempNode = tempNode.child.get(ch);
        }
        if (tempNode != null && tempNode.isEnd == false)
            return null;

        return tempNode;
    }

    public static void main(String[] args) {
        String[] input = {
                "s3://mybucket/some/path/2021/03/03/file.txt",
                "s3://mybucket/some/path/2021/03/04/file.txt",
                "s3://mybucket/some/path/2021/03/05/file.txt",
                "s3://mybucket/some/path/2021/03/06/file.txt",
                "s3://mybucket/some/path/2021/03/07/file.txt",
        };
        PrefixTree prefixTree = new PrefixTree();
        Random random = new Random();

        for(String key: input){
            prefixTree.put(key, random.nextInt(2)); // inserts 0-1 randomly
        }

        System.out.println(prefixTree.get(input[1]).value);

        // Update functionality demo
        prefixTree.put(input[1], prefixTree.get(input[1]).value+3);

        // value will be updated
        System.out.println(prefixTree.get(input[1]).value);

    }
}

Java 具有字符串键部分重用的内存映射

Java in-memory map with string key part reuse

java

dictionary

trie

prefix-tree