Python字典與雜湊：深入解析內部結構與應用

– 15 分鐘閱讀

Python 字典底層採用雜湊表實作，透過雜湊函式將鍵對映到雜湊值，再根據雜湊值找到對應的儲存位置。雜湊衝突是不可避免的，Python 使用開放定址法解決衝突，將衝突的鍵值對儲存在下一個可用位置。理解雜湊函式和衝突處理機制對於高效使用字典至關重要。Python 也允許自定義類別實作 __hash__() 方法，以控制物件的雜湊值，方便將自定義物件作為字典的鍵。標準函式庫提供了豐富的模組，例如 colorsys 模組可以進行色彩空間轉換，time 模組提供跨平臺的時間相關函式。Python 測試框架 unittest 對於確保程式碼品質至關重要，透過撰寫測試案例，可以驗證程式碼的正確性和可靠性。

雜湊衝突

雜湊衝突是指兩個不同值具有相同的雜湊值。這在設計雜湊函式時應儘量避免，因為它會影響字典的效能。

內建型別的雜湊函式

一些內建型別的雜湊函式非常簡單，如long型別：

>>> (401).__hash__()
401

對於更長的值，雜湊函式會更復雜：

>>> (401123124389798989898).__hash__()
2212283795829936375

許多內建型別使用Python的pyhash.c模組，該模組提供了以下輔助雜湊函式：

  • _Py_HashBytes(const void*, Py_ssize_t): 用於位元組串的雜湊。
  • _Py_HashDouble(double): 用於雙精確度浮點數的雜湊。
  • _Py_HashPointer(void*): 用於指標的雜湊。

例如，Unicode字串使用 _Py_HashBytes() 來對字串的位元組資料進行雜湊。

示例程式碼

下面是一個簡單的示例，展示瞭如何使用Python中的字典和雜湊：

# 建立一個字典
my_dict = {"name": "John", "age": 30}

# 存取字典中的值
print(my_dict["name"])  # 輸出：John

# 更新字典中的值
my_dict["age"] = 31
print(my_dict["age"])  # 輸出：31

# 刪除字典中的鍵值對
del my_dict["age"]
print(my_dict)  # 輸出：{'name': 'John'}

# 使用雜湊函式
print(hash("hello"))  # 輸出雜湊值

這個示例演示瞭如何建立、存取、更新和刪除字典中的鍵值對，以及如何使用雜湊函式取得一個字串的雜湊值。

Python中的字典提供了一種快速且靈活的方式來儲存和對映資料。透過使用雜湊表，字典能夠快速檢索和儲存資料。理解雜湊函式和雜湊衝突對於有效地使用字典至關重要。透過示例程式碼，我們可以看到如何使用字典和雜湊函式來解決實際問題。

自定義類別的雜湊函式

在 Python 中，使用者自定義的類別可以透過實作 __hash__() 方法來定義自己的雜湊函式。這個方法應該回傳一個整數值，代表該物件的雜湊值。

實作 __hash__() 方法

以下是一個簡單的例子，示範如何在一個自定義類別中實作 __hash__() 方法：

class User:
    def __init__(self, id: int, name: str, address: str):
        self._id = id

    def __hash__(self):
        return hash(self._id)

    @property
    def id(self):
        return self._id

在這個例子中，User 類別的 __hash__() 方法 simplemente 回傳 _id 屬性的雜湊值。這意味著兩個 User 物件如果具有相同的 _id 值，則它們的雜湊值也將相同。

使用自定義類別的雜湊值

一旦實作了 __hash__() 方法，您就可以使用自定義類別的物件作為字典的鍵或集合的元素：

bob = User(123884, "Bob Smith", "Townsville, QLD")
sally = User(123823, "Sally Smith", "Cairns, QLD")

near_reef = {bob: False, sally: True}
print(near_reef[bob])  # Output: False

在這個例子中，bob 和 sally 是兩個 User 物件，它們被用作字典 near_reef 的鍵。由於 User 類別實作了 __hash__() 方法，因此這些物件可以被用作字典的鍵。

集合和雜湊值

當您將自定義類別的物件新增到一個集合中時，Python 會使用它們的雜湊值來確定是否已經存在於集合中：

users = {bob, bob}
print(users)  # Output: {<__main__.User object at 0x10df244b0>}

在這個例子中，bob 物件被新增到集合 users 中兩次。由於 User 類別實作了 __hash__() 方法，因此 Python 可以使用它們的雜湊值來確定是否已經存在於集合中，並且只會保留一個副本。

瞭解Python字典的內部結構

Python字典（dictionary）是一種重要的資料結構，負責儲存和管理鍵值對。要了解Python字典的內部結構，我們需要深入探討其成員變數和相關函式。

字典的成員變數

Python字典的內部結構可以透過其成員變數來瞭解。主要的成員變數包括：

  • ma_keys: 一個PyDictKeysObject指標，指向字典的鍵表。
  • ma_used: 一個Py_ssize_t整數，表示字典中已使用的元素數量。
  • ma_values: 一個PyObject**指標，指向字典的值表（在分離模式下）。
  • ma_version_tag: 一個uint64_t整數，表示字典的版本號。

鍵表的結構

鍵表（PyDictKeysObject）是字典的一部分，負責儲存和管理鍵。鍵表的主要成員變數包括：

  • dk_entries: 一個PyDictKeyEntry陣列，儲存鍵值對。
  • dk_indices: 一個字元陣列，儲存鍵的雜湊值和索引。
  • dk_lookup: 一個函式指標，指向查詢函式。
  • dk_nentries: 一個Py_ssize_t整數，表示鍵表中已使用的元素數量。
  • dk_refcnt: 一個Py_ssize_t整數，表示鍵表的參照計數。

字典的查詢函式

字典的查詢函式（dk_lookup）是一個重要的函式，負責根據鍵值查詢對應的值。這個函式會根據鍵的雜湊值和索引在鍵表中查詢對應的鍵值對。

字典的分離模式

Python字典可以處於兩種模式：分離模式（separated）和合併模式（combined）。在分離模式下，字典的值會儲存在一個單獨的表中（ma_values），而在合併模式下，字典的值會儲存在鍵表中。

內容解密：
import sys

# 建立一個字典
d = {'a': 1, 'b': 2, 'c': 3}

# 取得字典的內部結構
print(sys.getsizeof(d))  # 輸出：280

# 取得字典的鍵表
print(d.keys())  # 輸出：dict_keys(['a', 'b', 'c'])

# 取得字典的值表
print(d.values())  # 輸出：dict_values([1, 2, 3])

圖表翻譯：

  flowchart TD
    A[建立字典] --> B[取得內部結構]
    B --> C[取得鍵表]
    C --> D[取得值表]
    D --> E[輸出結果]

這個圖表展示了建立一個字典、取得其內部結構、取得鍵表和值表、以及輸出結果的過程。

Python標準函式庫模組

Python的標準函式庫是一個龐大的模組集合，包含了各種功能的模組。這些模組可以分為兩類別：純Python模組和C語言模組。

純Python模組

純Python模組是指使用Python語言編寫的模組。這些模組通常存放在Lib目錄下，例如colorsys模組。colorsys模組提供了色彩轉換的功能，例如將RGB色彩轉換為HLS色彩。

C語言模組

C語言模組是指使用C語言編寫的模組。這些模組通常需要編譯成分享函式庫檔案，然後才能被Python呼叫。例如，numpy模組就是一個使用C語言編寫的模組，它提供了高效的數值運算功能。

模組的匯入和使用

要使用Python的標準函式庫模組，需要先匯入模組。可以使用import陳述式匯入模組，例如：

import colorsys

匯入模組後，可以使用模組中的函式和變數。例如：

colorsys.rgb_to_hls(255, 0, 0)

這個例子中，rgb_to_hls是colorsys模組中的一個函式，它可以將RGB色彩轉換為HLS色彩。

模組的結構

Python的標準函式庫模組通常都有一個特定的結構。每個模組都有一個對應的.py檔案，例如colorsys.py。在這個檔案中，定義了模組中的函式、變數和類別。

模組的優點

使用Python的標準函式庫模組有很多優點。首先，標準函式庫模組都是由Python開發團隊維護的，所以它們通常都很穩定和可靠。其次，標準函式庫模組都有一個統一的結構和命名規則，所以很容易學習和使用。最後，標準函式庫模組通常都包含了很多實用的功能，所以可以節省開發時間和提高開發效率。

色彩空間轉換：RGB至HLS

色彩空間基礎

在色彩科學中，色彩空間是用來描述色彩的數學模型。RGB（紅、綠、藍）色彩空間是一種常見的色彩空間，用於顯示器和其他電子裝置。然而，在某些應用中，HLS（色相、亮度、飽和度）色彩空間更為方便，因為它能夠更直觀地描述色彩的特性。

HLS色彩空間

HLS色彩空間由三個引陣列成：

  • H（色相）：描述色彩的基本色調，範圍從0到360度。
  • L（亮度）：描述色彩的明暗程度，範圍從0到1。
  • S（飽和度）：描述色彩的純度，範圍從0到1。

RGB至HLS轉換

以下是RGB至HLS的轉換過程：

def rgb_to_hls(r, g, b):
    """
    將RGB色彩空間轉換為HLS色彩空間。
    
    引數：
    r (float): 紅色分量，範圍從0到1。
    g (float): 綠色分量，範圍從0到1。
    b (float): 藍色分量，範圍從0到1。
    
    傳回：
    h (float): 色相，範圍從0到360度。
    l (float): 亮度，範圍從0到1。
    s (float): 飽和度，範圍從0到1。
    """
    
    # 找出最大和最小的色彩分量
    maxc = max(r, g, b)
    minc = min(r, g, b)
    
    # 計算亮度
    l = (minc + maxc) / 2.0
    
    # 如果最大和最小的色彩分量相同，則色相和飽和度為0
    if minc == maxc:
        return 0.0, l, 0.0
    
    # 計算飽和度
    if l <= 0.5:
        s = (maxc - minc) / (maxc + minc)
    else:
        s = (maxc - minc) / (2.0 - maxc - minc)
    
    # 計算色相
    rc = (maxc - r) / (maxc - minc)
    gc = (maxc - g) / (maxc - minc)
    bc = (maxc - b) / (maxc - minc)
    
    # 根據最大色彩分量的位置計算色相
    if r == maxc:
        h = (gc - bc) % 6
    elif g == maxc:
        h = (bc - rc) % 6
    else:
        h = (rc - gc) % 6
    
    # 將色相轉換為度數
    h = h * 60
    
    # 如果色相為負數，則將其轉換為正數
    if h < 0:
        h += 360
    
    return h, l, s

內容解密：

上述程式碼實作了RGB至HLS的轉換。首先，找到最大和最小的色彩分量，並計算亮度。然後，根據亮度的值計算飽和度。最後，根據最大色彩分量的位置計算色相，並將其轉換為度數。

圖表翻譯：

  flowchart TD
    A[RGB輸入] --> B[計算最大和最小色彩分量]
    B --> C[計算亮度]
    C --> D[計算飽和度]
    D --> E[計算色相]
    E --> F[輸出HLS]

此圖表展示了RGB至HLS轉換的流程。首先，輸入RGB值，然後計算最大和最小的色彩分量。接下來，計算亮度、飽和度和色相。最後，輸出HLS值。

Python模組與C模組的區別

Python的標準函式庫中包含了許多模組，其中有些是用Python編寫的，另外一些則是用C編寫的。用Python編寫的模組通常存放在Lib目錄下，而用C編寫的模組則存放在Modules目錄下。

Python模組

用Python編寫的模組通常是標準函式庫的一部分，例如math、random等模組。這些模組的原始碼存放在Lib目錄下，可以直接檢視和修改。例如，math模組的原始碼存放在Lib/math.py檔案中。

C模組

用C編寫的模組通常是Python直譯器的一部分，例如sys、__builtins__等模組。這些模組的原始碼存放在Modules目錄下，需要使用C編譯器編譯才能使用。例如，sys模組的原始碼存放在Modules/sysmodule.c檔案中。

內建模組

有一些內建模組是用C編寫的，例如__builtins__模組。這個模組包含了所有內建函式，例如print()、chr()等。當Python直譯器啟動時，會自動匯入這些內建函式。

print()函式的實作

當我們呼叫print()函式時，會發生以下步驟：

  1. 編譯器將字串常數"Hello, World"轉換為PyUnicodeObject物件。
  2. builtin_print()函式被呼叫，傳入一個引數和NULL的kwnames。
  3. file變數被設定為PyId_stdout，即標準輸出流的系統處理器。
  4. 每個引數被傳遞給file物件。
  5. 標準輸出流中增加了一個換行符（\n）。

以下是builtin_print()函式的實作程式碼：

static PyObject *
builtin_print(PyObject *self, PyObject *const *args,
              Py_ssize_t nargs, PyObject *kwnames)
{
   ...
    if (file == NULL || file == Py_None) {
        file = _PySys_GetObjectId(&PyId_stdout);
    }
   ...
    for (i = 0; i < nargs; i++) {
        if (i > 0) {
           ...
        }
    }
   ...
}

這個函式首先檢查是否需要使用標準輸出流，如果需要則設定file變數為標準輸出流的系統處理器。然後，函式遍歷所有引數，並將每個引數傳遞給file物件。最後，函式在標準輸出流中增加了一個換行符。

Python核心開發：時間模組與跨平臺實作

Python作為一種跨平臺的程式語言，其核心開發涉及到許多低層次的系統呼叫，以確保在不同的作業系統上都能夠順暢執行。時間模組（time module）就是其中一個非常重要的部分，因為它需要與作業系統的時間相關函式進行互動，以提供準確的時間資訊。

時間模組的實作

時間模組的實作根據作業系統的不同而有所區別。在Unix-like系統（如Linux和macOS）中，時間模組使用<sys/times.h>標頭檔案中的函式來取得時間資訊。這些函式提供了對系統時間的存取，允許Python程式獲得當前的時間、過去的時間間隔等資訊。

在Windows系統中，由於其時間函式的實作與Unix-like系統有所不同，Python的時間模組需要使用Windows API中的函式，如GetProcessTimes()，來取得時間資訊。這意味著時間模組的程式碼需要根據作業系統進行條件編譯，以確保在不同平臺上正確地編譯和執行。

條件編譯和多平臺支援

Python的原始碼中使用了條件編譯的技巧，以根據不同的作業系統選擇合適的實作。例如，在Modules/timemodule.c檔案中，可以看到以下程式碼：

#ifdef HAVE_SYS_TIMES_H
#include <sys/times.h>
#endif

#ifdef MS_WINDOWS
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include "pythread.h"
#endif /* MS_WINDOWS */

這段程式碼根據作業系統是否支援<sys/times.h>標頭檔案（主要在Unix-like系統中）或是否是Windows系統，選擇包含不同的標頭檔案和定義不同的宏，以實作時間模組的功能。

時間模組的API

時間模組提供了一個統一的API給Python程式使用，無論底層作業系統如何。這個API包括瞭如time(),sleep(),process_time()等函式，它們分別用於取得當前的時間、暫停執行一段時間和測量程式的執行時間。

測試和驗證

為了確保Python核心和標準函式庫在不同平臺上的正確性和可靠性，Python專案提供了一個全面的測試套件。這個套件位於Lib/test目錄中，包含了大量的測試案例，用於驗證Python的各個方面，包括但不限於基礎型別、運算子、控制結構、函式、例外處理等。

這些測試可以透過執行特定的指令碼來執行，例如在Windows上，可以使用rt.bat指令碼來執行測試套件。這個過程可以幫助開發者確保他們對Python核心和標準函式庫的修改沒有引入新的錯誤，並且保證了跨平臺的一致性。

執行Python測試的

環境設定

在開始執行Python測試之前，需要確保您的環境已經正確設定。這包括安裝正確版本的Python、設定PATH變數以及確保所有必要的依賴項都已經安裝。

執行測試

要執行Python測試，可以使用以下命令：

rt.bat -q -d -x64

這個命令會啟動測試過程，並且會顯示測試的進度和結果。

測試結果

測試結果會顯示每個測試案例的執行結果，包括透過和失敗的案例。例如：

0:00:00 [ 1/420] test_grammar
0:00:00 [ 2/420] test_opcodes
0:00:00 [ 3/420] test_dict
0:00:00 [ 4/420] test_builtin
...

問題排除

如果您遇到任何問題，可以嘗試以下步驟：

  • 檢查您的環境設定是否正確。
  • 確保所有必要的依賴項都已經安裝。
  • 檢查測試結果以瞭解哪些測試案例失敗了。

在Linux和MacOS上執行測試

在Linux和MacOS上，可以使用以下命令來執行測試：

make test

這個命令會編譯和執行測試，並且會顯示測試的進度和結果。

執行Python測試

Python提供了一個內建的測試框架，允許您執行各種測試以確保Python的正確性和穩定性。以下是如何執行Python測試的步驟：

使用命令列執行測試

您可以使用以下命令執行Python測試：

$./python -m test

這將執行Python的標準測試套件，包括多個測試案例。

測試選項

Python提供了多個測試選項，包括：

  • test: 執行標準測試套件
  • testall: 執行完整的測試套件，包括所有測試案例
  • quicktest: 執行快速測試套件，排除耗時的測試案例
  • testuniversal: 執行測試套件，適用於OSX的通用建築
  • coverage: 編譯和執行測試，使用gcov進行覆寫率分析
  • coverage-lcov: 生成HTML格式的覆寫率報告

執行特定測試

您可以使用以下命令執行特定的測試：

$./python -m test <test_name>

將 <test_name> 替換為您要執行的測試名稱。

列出可用的測試

您可以使用以下命令列出可用的測試：

$./python -m test --list-tests

這將顯示可用的測試清單。

測試旗標

一些測試需要特殊的旗標才能執行。例如，IDLE的測試需要圖形介面（GUI）。您可以使用以下命令檢視可用的旗標：

$./python -m test --help

這將顯示可用的旗標和選項。

執行特定測試

要執行特定的測試，需要在命令列中指定要執行的測試集。以下是Linux或macOS下的範例：

$./python -m test test_webbrowser

執行測試結果

執行測試後，會顯示測試結果，包括測試是否成功、耗時等資訊。

0:00:00 load avg: 2.74 [1/1] test_webbrowser
== Tests result: SUCCESS ==
1 test OK.
Total duration: 117 ms
Tests result: SUCCESS

Windows下的執行方式

在Windows下，可以使用以下命令執行測試：

> rt.bat -q -d -x64 test_webbrowser

詳細測試結果

如果需要檢視詳細的測試結果，包括每個測試案例的執行情況，可以使用 -v 引數：

$./python -m test test_webbrowser -v

這將顯示更詳細的測試結果，包括測試環境、測試案例的執行情況等。

== CPython 3.9
== macOS-10.14.3-x86_64-i386-64bit little-endian
== cwd: /Users/anthonyshaw/cpython/build/test_python_24562

測試框架與Python測試

Python的測試框架是用於確保程式碼正確性和可靠性的重要工具。其中，unittest模組是Python標準函式庫中的一部分，提供了豐富的測試功能。

測試類別與方法

在unittest中，測試類別繼承自unittest.TestCase。每個測試方法都以test開頭，例如test_casefold。這些方法使用斷言（assert）來驗證程式碼的行為是否符合預期。

測試執行

要執行測試，可以使用unittest.main()函式。這個函式會自動發現和執行所有繼承自unittest.TestCase的類別中的測試方法。

測試結果

測試結果會顯示測試是否透過或失敗。如果所有測試都透過，則會顯示「OK」的訊息。否則，會顯示錯誤訊息，指出哪些測試失敗了。

測試框架結構

測試框架通常按照模組或套件進行組織。例如，Unicode相關的測試放在Lib/test/test_unicode.py檔案中，而非同步程式設計相關的測試放在Lib/test/test_asyncio.py檔案中。

實際應用

在實際應用中，測試是確保程式碼品質的重要步驟。透過寫測試，我們可以確保程式碼按照預期工作，並且在未來的修改中不會引入錯誤。

相關資源

如果您是測試新手，Real Python的「Getting Started With Testing in Python」文章是一個很好的入門資源。

Python 字典與其內部雜湊機制、測試框架的深度解析，體現了程式語言設計的精妙與複雜性。透過剖析內建型別、自定義類別的雜湊函式，以及雜湊衝突的處理，我們能更有效地運用字典結構，提升程式碼效能。同時，理解字典的內部結構，包含鍵表、查詢函式、分離模式等核心元件，有助於我們更精準地預估記憶體使用，進而編寫更最佳化的程式碼。

Python 標準函式庫模組的多樣性，從色彩空間轉換的 colorsys 模組到時間模組的跨平臺實作，展現了其強大的生態系統和跨平臺適應性。深入理解 Python 模組與 C 模組的區別、模組的匯入和使用方式，以及色彩空間轉換的實作細節，有助於開發者更有效地利用現有資源，避免重複造輪子。尤其在時間模組部分，Python 針對不同作業系統的條件編譯技巧，更體現了其跨平臺相容性的核心設計理念。

此外，文章詳盡地介紹了執行 Python 測試的流程，從環境設定、執行方式到結果判讀，都提供了清晰的指引。尤其針對 Linux、macOS 和 Windows 等不同平臺的執行方式，以及如何執行特定測試、檢視詳細測試結果，都給予了開發者實務上的指導。這對於確保程式碼品質、提升開發效率至關重要。

玄貓認為，深入理解 Python 的底層機制和標準函式庫，並善用其測試框架，是成為一名 Python 高手的必經之路。未來，隨著 Python 生態的持續發展，掌握這些核心知識將更加重要。持續學習、探索 Python 的更多可能性，才能在技術浪潮中保持競爭力。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。