我在地圖中有數萬條記錄。映射鍵是類似s3://mybucket/some/path/2021/03/03/file.txt, 的字串s3://mybucket/some/path/2021/03/04/file.txt，值是0or 1。目前我用的是HashMap但是記憶體占用太高了，我想減少它。
我正在尋找一種關鍵值并利用關鍵部分可重用性的東西。自然而然想到的是使用一些樹結構來存盤前綴。
有人可以指出適當的實作，最好是輕量級的嗎？
uj5u.com熱心網友回復：
APrefix Tree是一種可能的解決方案，在空間復雜性方面將是輕量級的。這是using的Java實作。我用的是我不知道的字母大小。如果您確定字典中的字母大小，您絕對可以使用固定長度。只有當標記字串的結尾時，每個才會存盤鍵的 。當您找到存盤最后一個密鑰的 時，您就可以訪問;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);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/373960.html
下一篇：用最大值更新字典鍵