hash_dict¶
ソースコード¶
from titan_pylib.data_structures.dict.hash_dict import HashDict
展開済みコード¶
1# from titan_pylib.data_structures.dict.hash_dict import HashDict
2import random
3from typing import Iterator, Any, Final
4
5_titan_pylib_HashDict_K: Final[int] = 0x517CC1B727220A95
6
7
8class HashDict:
9 """ハッシュテーブルです。
10 組み込み辞書の ``dict`` よりやや遅いです。
11 """
12
13 def __init__(self, e: int = -1, default: Any = 0, reserve: int = -1) -> None:
14 """
15 Args:
16 e (int, optional): ``int`` 型で ``key`` として使用しない値です。
17 ``key`` を ``int`` 型以外のもので指定したいときは ``_hash(key) -> int`` 関数をいじってください。
18 default (Any, optional): 存在しないキーにアクセスしたときの値です。
19 """
20 # e: keyとして使わない値
21 # default: valのdefault値
22 self._keys: list[int] = [e]
23 self._vals: list[Any] = [default]
24 self._msk: int = 0
25 self._xor: int = random.getrandbits(1)
26 if reserve > 0:
27 self._keys: list[int] = [e] * (1 << (reserve.bit_length()))
28 self._vals: list[Any] = [default] * (1 << (reserve.bit_length()))
29 self._msk = (1 << (len(self._keys) - 1).bit_length()) - 1
30 self._xor = random.getrandbits((len(self._keys) - 1).bit_length())
31 self._e: int = e
32 self._len: int = 0
33 self._default: Any = default
34
35 def _rebuild(self) -> None:
36 old_keys, old_vals, _e = self._keys, self._vals, self._e
37 self._keys = [_e] * (2 * len(old_keys))
38 self._vals = [self._default] * len(self._keys)
39 self._len = 0
40 self._msk = (1 << (len(self._keys) - 1).bit_length()) - 1
41 self._xor = random.getrandbits((len(self._keys) - 1).bit_length())
42 for i in range(len(old_keys)):
43 if old_keys[i] != _e:
44 self.set(old_keys[i], old_vals[i])
45
46 def _hash(self, key: int) -> int:
47 return (
48 ((((key >> 32) & self._msk) ^ (key & self._msk) ^ self._xor))
49 * (_titan_pylib_HashDict_K & self._msk)
50 ) & self._msk
51
52 def get(self, key: int, default: Any = None) -> Any:
53 """
54 キーが ``key`` の値を返します。
55 存在しない場合、引数 ``default`` に ``None`` 以外を指定した場合は ``default`` が、
56 そうでない場合はコンストラクタで設定した ``default`` が返ります。
57
58 期待 :math:`O(1)` です。
59 """
60 assert (
61 key != self._e
62 ), f"KeyError: HashDict.get({key}, {default}), {key} cannot be equal to {self._e}"
63 l, _keys, _e = len(self._keys), self._keys, self._e
64 h = self._hash(key)
65 while True:
66 x = _keys[h]
67 if x == _e:
68 return self._vals[h] if default is None else default
69 if x == key:
70 return self._vals[h]
71 h = 0 if h == l - 1 else h + 1
72
73 def add(self, key: int, val: Any, default: Any) -> None:
74 assert (
75 key != self._e
76 ), f"KeyError: HashDict.add({key}, {default}), {key} cannot be equal to {self._e}"
77 l, _keys, _e = len(self._keys), self._keys, self._e
78 h = self._hash(key)
79 while True:
80 x = _keys[h]
81 if x == _e:
82 self._vals[h] = val
83 return
84 if x == key:
85 self._vals[h] += val
86 return
87 h = 0 if h == l - 1 else h + 1
88
89 def set(self, key: int, val: Any) -> None:
90 """キーを ``key`` として ``val`` を格納します。
91 ``key`` が既に存在している場合は上書きされます。
92
93 期待 :math:`O(1)` です。
94 """
95 assert (
96 key != self._e
97 ), f"KeyError: HashDict.set({key}, {val}), {key} cannot be equal to {self._e}"
98 l, _keys, _e = len(self._keys), self._keys, self._e
99 l -= 1
100 h = self._hash(key)
101 while True:
102 x = _keys[h]
103 if x == _e:
104 _keys[h] = key
105 self._vals[h] = val
106 self._len += 1
107 if 2 * self._len > len(self._keys):
108 self._rebuild()
109 return
110 if x == key:
111 self._vals[h] = val
112 return
113 h = 0 if h == l else h + 1
114
115 def __contains__(self, key: int) -> bool:
116 """存在判定です。
117
118 期待 :math:`O(1)` です。
119
120 Returns:
121 bool: ``key`` が存在すれば ``True`` を、そうでなければ ``False`` を返します。
122 """
123 assert (
124 key != self._e
125 ), f"KeyError: {key} in HashDict, {key} cannot be equal to {self._e}"
126 l, _keys, _e = len(self._keys), self._keys, self._e
127 h = self._hash(key)
128 while True:
129 x = _keys[h]
130 if x == _e:
131 return False
132 if x == key:
133 return True
134 h += 1
135 if h == l:
136 h = 0
137
138 __getitem__ = get
139 __setitem__ = set
140
141 def keys(self) -> Iterator[int]:
142 """``key 集合`` を列挙するイテレータです。"""
143 _keys, _e = self._keys, self._e
144 for i in range(len(_keys)):
145 if _keys[i] != _e:
146 yield _keys[i]
147
148 def values(self) -> Iterator[Any]:
149 """``val 集合`` を列挙するイテレータです。"""
150 _keys, _vals, _e = self._keys, self._vals, self._e
151 for i in range(len(_keys)):
152 if _keys[i] != _e:
153 yield _vals[i]
154
155 def items(self) -> Iterator[tuple[int, Any]]:
156 """``key とそれに対応する val のタプル`` を列挙するイテレータです。"""
157 _keys, _vals, _e = self._keys, self._vals, self._e
158 for i in range(len(_keys)):
159 if _keys[i] != _e:
160 yield _keys[i], _vals[i]
161
162 def __str__(self):
163 return "{" + ", ".join(map(lambda x: f"{x[0]}: {x[1]}", self.items())) + "}"
164
165 def __len__(self):
166 return self._len
仕様¶
- class HashDict(e: int = -1, default: Any = 0, reserve: int = -1)[source]¶
Bases:
objectハッシュテーブルです。 組み込み辞書の
dictよりやや遅いです。- __contains__(key: int) bool[source]¶
存在判定です。
期待 \(O(1)\) です。
- Returns:
keyが存在すればTrueを、そうでなければFalseを返します。- Return type:
bool
- __getitem__(key: int, default: Any = None) Any¶
キーが
keyの値を返します。 存在しない場合、引数defaultにNone以外を指定した場合はdefaultが、 そうでない場合はコンストラクタで設定したdefaultが返ります。期待 \(O(1)\) です。
- __setitem__(key: int, val: Any) None¶
キーを
keyとしてvalを格納します。keyが既に存在している場合は上書きされます。期待 \(O(1)\) です。
- get(key: int, default: Any = None) Any[source]¶
キーが
keyの値を返します。 存在しない場合、引数defaultにNone以外を指定した場合はdefaultが、 そうでない場合はコンストラクタで設定したdefaultが返ります。期待 \(O(1)\) です。