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

Question

我在地图中有数万条记录。映射键是字符串，如s3://mybucket/some/path/2021/03/03/file.txt, s3://mybucket/some/path/2021/03/04/file.txt，值是0or 1。到目前为止我使用 HashMap 但内存使用率太高，我想减少它。

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

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

Answer 1

APrefix Tree是一种可能的解决方案，在空间复杂度方面将是轻量级的。这是一个using的Java实现。我用 a表示，因为我不确定字母的大小。如果您确定字典中的字母大小，您绝对可以使用固定长度。仅当标记字符串的结尾时，每个都将存储密钥的 。当您找到存储密钥的最后一个时，您可以访问;Prefix TreeTrieHashMapchildchild TrieNodeTrieNodevalueTrieNodeTrieNodecharactervalue

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);

    }
}