【python】字典数据结构的设计原理学习
<h1>先说结论：</h1><p>python的dict，底层是哈希表（hash table）与开放寻址方案（二次探测 + 伪随机跳跃）</p>
<p>其中，</p>
<h3>核心结构：哈希表是一个“数组”</h3>
<p>每个 dict 底层对应一块数组（table），数组每个槽位（slot）可能存一个 key-value。</p>
<div class="cnblogs_Highlighter">
<pre class="brush:python;gutter:true;">index: 0 1 2 3 4 5 6 7
value:[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]</pre>
</div>
<p>任何输入的key 会被哈希（hash(key)）</p>
<div class="cnblogs_Highlighter">
<pre class="brush:python;gutter:true;">d["abc"] = 123
# python会计算
h = hash("abc") →得到一个整数，如 918273645
slot = h % table_size →如 918273645 % 8 = 5
</pre>
</div>
<p>于是 key 放到 <strong data-start="624" data-end="632">槽位 5</strong></p>
<div class="cnblogs_Highlighter">
<pre class="brush:python;gutter:true;">index: 0 1 2 3 4 5 6 7
value:[ ] [ ] [ ] [ ] [ ] [('abc',123)] [ ] [ ]</pre>
</div>
<p>如果计算出的槽位已经被占用，dict 不会链表化存储，而是 继续找下一个空槽位，其中会使用 开放寻址（Open Addressing）</p>
<div class="cnblogs_Highlighter">
<pre class="brush:python;gutter:true;">slot 6 空？ → 放这里
slot 6 也有人？ → 看 slot 7
</pre>
</div>
<p> </p>
<p>dict 会控制“负载因子”（使用率），比如如果槽位使用率超过 ~2/3，自动扩容。扩容后空间很大，冲突变少，因此 dict 的性能保持 O(1)。</p>
<p data-start="1085" data-end="1090">扩容操作：</p>
<ul>
<li data-start="1085" data-end="1090">table 大小扩成原来的 2 倍</li>
<li data-start="1112" data-end="1143">
<p data-start="1114" data-end="1143">所有 key 重新哈希并放入新 table（rehash）</p>
</li>
</ul>
<p> </p>
<p>看具体的应用场景：使用dict进行查找、插入操作，时间复杂度是O(1)</p>
<p>1. 查找过程</p>
<p data-start="1337" data-end="1349">查找 <code data-start="1340" data-end="1348">d</code>：</p>
<ol data-start="1351" data-end="1455">
<li data-start="1351" data-end="1366">
<p data-start="1354" data-end="1366">计算 hash(key)</p>
</li>
<li data-start="1367" data-end="1399">
<p data-start="1370" data-end="1399">定位槽位 slot = hash % table_size</p>
</li>
<li data-start="1400" data-end="1455">
<p data-start="1403" data-end="1419">看到槽位里是不是这个 key</p>
<ul data-start="1423" data-end="1455">
<li data-start="1423" data-end="1433">
<p data-start="1425" data-end="1433">是 → 找到</p>
</li>
<li data-start="1437" data-end="1455">
<p data-start="1439" data-end="1455">否 → 使用开放寻址规则继续探测</p>
</li>
</ul>
</li>
</ol>
<p>那么影响时间长短的，就要看hash算法的底层原理了，hash函数大致是位运算+随机化</p>
<div class="cnblogs_code">
<pre><span style="color: rgba(0, 128, 128, 1)">1</span> adict =<span style="color: rgba(0, 0, 0, 1)"> {}
</span><span style="color: rgba(0, 128, 128, 1)">2</span> adict=<span style="color: rgba(0, 0, 0, 1)">value
</span><span style="color: rgba(0, 128, 128, 1)">3</span> <span style="color: rgba(0, 0, 255, 1)">if</span> i <span style="color: rgba(0, 0, 255, 1)">not</span> <span style="color: rgba(0, 0, 255, 1)">in</span> adict: <span style="color: rgba(0, 128, 0, 1)">#</span><span style="color: rgba(0, 128, 0, 1)"> i是否属于adict的key</span></pre>
</div>
<p> </p>
<p> </p>
<p> </p>
<p> </p>
<p> </p>
<p><span style="background-color: rgba(255, 255, 255, 1); font-family: "PingFang SC", "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px"> </span></p>
<p> </p><br><br>
来源：https://www.cnblogs.com/xiaojp65536/p/19299732
頁:
[1]