# 字典就像一本真實(shí)的詞典（或電話簿）
# - 你要查"Python"這個(gè)詞（鍵）
# - 詞典告訴你它的釋義（值）
# - 你不需要從頭翻到尾（O(n)），而是可以根據(jù)索引快速定位（O(1)）

# 在代碼中
word_meaning = {
    'Python': '一種高級(jí)編程語言',
    'dict': '字典，鍵值對(duì)映射結(jié)構(gòu)',
    'API': '應(yīng)用程序編程接口',
}

print(word_meaning['Python'])  # 一種高級(jí)編程語言
print(word_meaning['API'])     # 應(yīng)用程序編程接口

# 特征一：鍵值對(duì)存儲(chǔ)
person = {
    'name': '小明',
    'age': 25,
    'city': '北京',
    'job': '工程師',
}

# 特征二：通過鍵訪問值（O(1)平均時(shí)間復(fù)雜度）
print(person['name'])  # 小明
print(person['age'])   # 25

# 特征三：鍵必須是不可變類型（可哈希）
# 字符串、數(shù)字、元組（不含可變元素）可以作為鍵
valid_keys = {
    'string': 1,
    42: 2,
    3.14: 3,
    True: 4,
    (1, 2): 5,
}

# 特征四：鍵是唯一的（后添加的會(huì)覆蓋前面的）
d = {'a': 1, 'b': 2, 'a': 999}
print(d)  # {'a': 999, 'b': 2}（'a'被覆蓋了）

# 特征五：Python 3.7+ 字典保持插入順序
d = {}
d['c'] = 3
d['a'] = 1
d['b'] = 2
print(list(d.keys()))  # ['c', 'a', 'b']（按插入順序）
# 這是Python 3.7+的官方保證

# 空字典
empty = {}
print(empty)  # {}

# 帶初始數(shù)據(jù)的字典
person = {'name': '小明', 'age': 25, 'city': '北京'}
print(person)  # {'name': '小明', 'age': 25, 'city': '北京'}

# 嵌套字典
config = {
    'database': {
        'host': 'localhost',
        'port': 5432,
    },
    'cache': {
        'host': 'redis://localhost',
        'port': 6379,
    },
}
print(config['database']['host'])  # localhost

# 方式一：關(guān)鍵字參數(shù)（鍵必須是合法標(biāo)識(shí)符）
d1 = dict(name='小明', age=25, city='北京')
print(d1)  # {'name': '小明', 'age': 25, 'city': '北京'}

# 這種方式的限制：鍵必須是合法的Python標(biāo)識(shí)符
# d = dict(1='one')  # SyntaxError

# 方式二：可迭代對(duì)象（每個(gè)元素是(key, value)對(duì)）
d2 = dict([('name', '小明'), ('age', 25), ('city', '北京')])
print(d2)  # {'name': '小明', 'age': 25, 'city': '北京'}

# 方式三：zip組合兩個(gè)列表
keys = ['name', 'age', 'city']
values = ['小明', 25, '北京']
d3 = dict(zip(keys, values))
print(d3)  # {'name': '小明', 'age': 25, 'city': '北京'}

# 方式四：混合使用
d4 = dict(name='小明', age=25)  # 關(guān)鍵字參數(shù)
d4.update({'city': '北京'})
print(d4)  # {'name': '小明', 'age': 25, 'city': '北京'}

# 基本推導(dǎo)式
squares = {x: x ** 2 for x in range(6)}
print(squares)  # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

# 帶條件的推導(dǎo)式
even_squares = {x: x ** 2 for x in range(10) if x % 2 == 0}
print(even_squares)  # {0: 0, 2: 4, 4: 16, 6: 36, 8: 64}

# 從兩個(gè)列表推導(dǎo)
keys = ['name', 'age', 'city']
values = ['小明', 25, '北京']
d = {k: v for k, v in zip(keys, values)}
print(d)  # {'name': '小明', 'age': 25, 'city': '北京'}

# 轉(zhuǎn)換現(xiàn)有字典
original = {'a': 1, 'b': 2, 'c': 3}
reversed_dict = {v: k for k, v in original.items()}
print(reversed_dict)  # {1: 'a', 2: 'b', 3: 'c'}

# 過濾字典
scores = {'小明': 85, '小紅': 92, '小剛': 78, '小李': 95}
passing = {name: score for name, score in scores.items() if score >= 90}
print(passing)  # {'小紅': 92, '小李': 95}

# fromkeys()：用相同的值初始化多個(gè)鍵
keys = ['a', 'b', 'c', 'd']
d = dict.fromkeys(keys, 0)
print(d)  # {'a': 0, 'b': 0, 'c': 0, 'd': 0}

# 不指定值時(shí)默認(rèn)None
d2 = dict.fromkeys(['x', 'y', 'z'])
print(d2)  # {'x': None, 'y': None, 'z': None}

# ?? fromkeys的陷阱：可變默認(rèn)值
# d3 = dict.fromkeys(['a', 'b'], [])
# d3['a'].append(1)
# print(d3)  # {'a': [1], 'b': [1]} ← 兩個(gè)鍵共享同一個(gè)列表！

# 如果每個(gè)值需要獨(dú)立的對(duì)象，用推導(dǎo)式
d3 = {k: [] for k in ['a', 'b']}
d3['a'].append(1)
print(d3)  # {'a': [1], 'b': []} ← 各自獨(dú)立

# 從Counter創(chuàng)建
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
counter = Counter(words)
print(dict(counter))  # {'apple': 3, 'banana': 2, 'cherry': 1}

# 從JSON字符串創(chuàng)建
import json
json_str = '{"name": "小明", "age": 25, "scores": [85, 92, 78]}'
data = json.loads(json_str)
print(data)  # {'name': '小明', 'age': 25, 'scores': [85, 92, 78]}

# 字典的底層實(shí)現(xiàn)是哈希表（Hash Table）
# 核心思想：通過哈希函數(shù)將任意鍵映射到一個(gè)固定范圍的整數(shù)
# 這個(gè)整數(shù)就是數(shù)據(jù)存儲(chǔ)的位置索引

# 簡化模型：
# 1. 計(jì)算鍵的哈希值 hash(key)
# 2. 將哈希值映射到內(nèi)部數(shù)組的索引
# 3. 在索引位置存儲(chǔ)/查找值

# 這就是為什么字典查找是O(1)——不需要遍歷，直接定位

# 展示哈希值
print(hash('hello'))     # 某個(gè)很大的整數(shù)（每次運(yùn)行可能不同）
print(hash(42))          # 42（整數(shù)的哈希值通常等于自身）
print(hash((1, 2, 3)))   # 某個(gè)整數(shù)
# print(hash([1, 2, 3])) # TypeError: unhashable type: 'list'

# 哈希沖突：不同的鍵可能產(chǎn)生相同的哈希值（或映射到相同的索引）
# Python的字典使用"開放尋址法"解決沖突

# 你不需要手動(dòng)處理哈希沖突——Python已經(jīng)搞定了
# 但你需要知道：哈希沖突會(huì)影響性能
# 如果所有鍵的哈希值都相同（極端情況），字典退化為O(n)

# 正常情況：O(1)查找
# 最壞情況：O(n)查找（極少發(fā)生，需要有嚴(yán)重bug的哈希函數(shù)）

# 字典的鍵必須滿足兩個(gè)條件：
# 1. 可哈希（hashable）——實(shí)現(xiàn)了 __hash__ 方法
# 2. 可比較相等——實(shí)現(xiàn)了 __eq__ 方法

# 可哈希的類型：
print(hash('hello'))     # 字符串 ?
print(hash(42))          # 整數(shù) ?
print(hash(3.14))        # 浮點(diǎn)數(shù) ?
print(hash(True))        # 布爾值 ?
print(hash((1, 2, 3)))  # 元組（全不可變元素） ?
print(hash(None))        # None ?

# 不可哈希的類型：
# hash([1, 2, 3])       # 列表 ?
# hash({'a': 1})         # 字典 ?
# hash({1, 2, 3})        # 集合 ?
# hash((1, [2, 3]))      # 包含可變元素的元組 ?


# 自定義對(duì)象默認(rèn)是可哈希的（除非定義了__eq__）
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

p = Point(1, 2)
print(hash(p))  # 有哈希值（基于對(duì)象id）

# 但如果定義了__eq__，就需要同時(shí)定義__hash__

# 關(guān)鍵原則：相等的對(duì)象必須有相等的哈希值
# a == b  ?  hash(a) == hash(b)

# Python 3.6+字典使用更緊湊的內(nèi)存布局
# 官方在3.7中保證了插入順序

# 舊實(shí)現(xiàn)（Python 3.5及以前）
# - 使用稀疏表
# - 內(nèi)存效率較低
# - 不保證順序

# 新實(shí)現(xiàn)（Python 3.6+）
# - 使用稠密表+索引表
# - 內(nèi)存減少20-25%
# - 保持插入順序（3.7正式保證）

import sys

# 對(duì)比空字典在不同版本的大?。ú豢芍苯訉?duì)比，僅供參考）
d = {}
print(f'空字典內(nèi)存: {sys.getsizeof(d)} 字節(jié)')

# 添加一些數(shù)據(jù)
for i in range(100):
    d[f'key_{i}'] = i
print(f'100元素的字典: {sys.getsizeof(d)} 字節(jié)')

# 可以作為字典鍵的類型（不可變 + 可哈希）

# 字符串（最常用）
d = {'name': '小明'}

# 數(shù)字（整數(shù)、浮點(diǎn)數(shù)）
d = {1: 'one', 2: 'two', 3.14: 'pi'}

# 布爾值（True=1, False=0——注意可能與數(shù)字鍵沖突）
d = {True: 'yes', False: 'no'}
print(d)  # {True: 'yes', False: 'no'}

# 元組（所有元素都不可變）
d = {(1, 2): 'point A', (3, 4): 'point B'}

# frozenset（不可變集合）
d = {frozenset([1, 2]): 'set12', frozenset([3, 4]): 'set34'}

# None
d = {None: 'nothing'}

# 自定義對(duì)象（默認(rèn)可哈希）
class User:
    def __init__(self, name):
        self.name = name

u1 = User('小明')
d = {u1: '用戶數(shù)據(jù)'}
print(d[u1])  # 用戶數(shù)據(jù)

# 字符串是字典鍵的絕對(duì)主力——90%以上的字典都用字符串作鍵
# 原因：人類可讀、方便序列化（JSON）、適合配置和API

# 關(guān)鍵字參數(shù)語法要求鍵是合法標(biāo)識(shí)符
config = dict(host='localhost', port=8080, debug=True)

# 字符串鍵支持的關(guān)鍵字參數(shù)創(chuàng)建
person = {'name': '小明', 'age': 25}
# 以下三種方式等價(jià)：
print(person['name'])
print(person.get('name'))
# 但person.name不行（對(duì)象屬性語法）

# Python 3.8+ 如果鍵是字符串且不含特殊字符，可用更簡潔的方式
# 普通情況還是用 [] 或 get()

# 字典最常遇到的錯(cuò)誤之一：KeyError
d = {'name': '小明', 'age': 25}

# print(d['city'])  # KeyError: 'city'

# 方法一：get()——最常用
city = d.get('city', '未知')
print(city)  # 未知

# 方法二：in 檢查
if 'city' in d:
    city = d['city']
else:
    city = '未知'

# 方法三：setdefault()——獲取值，如果不存在則設(shè)置默認(rèn)值
city = d.setdefault('city', '北京')
print(city)  # 北京
print(d)     # {'name': '小明', 'age': 25, 'city': '北京'}

# setdefault的妙用——分組
words = ['apple', 'banana', 'apricot', 'cherry', 'blueberry']
by_first_letter = {}
for word in words:
    first = word[0]
    by_first_letter.setdefault(first, []).append(word)
print(by_first_letter)
# {'a': ['apple', 'apricot'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

# 方法四：collections.defaultdict（更優(yōu)雅的分組方式）
from collections import defaultdict

by_first_letter = defaultdict(list)
for word in words:
    by_first_letter[word[0]].append(word)
print(dict(by_first_letter))

# 字典操作的平均時(shí)間復(fù)雜度

# O(1) 操作：
# - d[key]：通過鍵獲取值
# - d[key] = value：設(shè)置鍵值對(duì)
# - del d[key]：刪除鍵值對(duì)
# - key in d：檢查鍵是否存在

# O(n) 操作：
# - for key in d：遍歷（O(n)）
# - len(d)：獲取長度（O(1)——字典維護(hù)了計(jì)數(shù)）
# - d.clear()：清空（O(n)——需要釋放所有元素）
# - d.copy()：淺拷貝（O(n)）

# 實(shí)際性能測試
import time

n = 1000000

# 創(chuàng)建大字典
d = {i: i ** 2 for i in range(n)}

# 查找——O(1)
start = time.perf_counter()
for _ in range(1000000):
    _ = d[500000]
t_lookup = time.perf_counter() - start
print(f'100萬次查找: {t_lookup:.3f}秒')
print(f'每次查找: {t_lookup / 1000000 * 1e9:.1f}納秒')

# 檢查存在——O(1)
start = time.perf_counter()
for _ in range(1000000):
    _ = 500000 in d
t_check = time.perf_counter() - start
print(f'100萬次in檢查: {t_check:.3f}秒')

import time

n = 10000

# 創(chuàng)建數(shù)據(jù)
lst = list(range(n))
d = {i: True for i in range(n)}

# 列表查找（O(n)）
start = time.perf_counter()
for _ in range(10000):
    _ = 9999 in lst
t_list = time.perf_counter() - start

# 字典查找（O(1)）
start = time.perf_counter()
for _ in range(10000):
    _ = 9999 in d
t_dict = time.perf_counter() - start

print(f'列表in查找: {t_list:.4f}秒')
print(f'字典in查找: {t_dict:.4f}秒')
print(f'字典比列表快 {t_list / t_dict:.0f} 倍')
# 隨著n增大，字典的優(yōu)勢更加明顯

d = {'name': '小明', 'age': 25, 'city': '北京'}

# keys()——鍵視圖
keys = d.keys()
print(keys)  # dict_keys(['name', 'age', 'city'])
print(type(keys))  # <class 'dict_keys'>

# values()——值視圖
values = d.values()
print(values)  # dict_values(['小明', 25, '北京'])

# items()——鍵值對(duì)視圖
items = d.items()
print(items)  # dict_items([('name', '小明'), ('age', 25), ('city', '北京')])

# 視圖是動(dòng)態(tài)的——能反映字典的變化！
d['job'] = '工程師'
print(keys)  # dict_keys(['name', 'age', 'city', 'job'])（自動(dòng)更新?。?

d = {'a': 1, 'b': 2, 'c': 3}

# 視圖支持迭代
for key in d.keys():
    print(key)

for value in d.values():
    print(value)

for key, value in d.items():
    print(f'{key} = {value}')

# 視圖支持成員檢查
print('a' in d.keys())    # True
print(1 in d.values())    # True
print(('a', 1) in d.items())  # True

# 視圖支持集合操作（keys()和items()）
keys = d.keys()
print(keys & {'a', 'c', 'e'})  # {'a', 'c'}（交集）
print(keys | {'d', 'e'})       # {'a', 'b', 'c', 'd', 'e'}（并集）
print(keys - {'a'})            # {'b', 'c'}（差集）
print(keys ^ {'a', 'd'})       # {'b', 'c', 'd'}（對(duì)稱差）

# values()通常不支持集合操作（因?yàn)橹悼赡苤貜?fù)且可能是不可哈希的）

# 用字典構(gòu)建查找表替代多個(gè)if-elif
def get_status_text(status_code):
    """這種寫法比if-elif鏈更清晰高效"""
    status_map = {
        200: '成功',
        301: '永久重定向',
        404: '未找到',
        500: '服務(wù)器錯(cuò)誤',
        502: '網(wǎng)關(guān)錯(cuò)誤',
        503: '服務(wù)不可用',
    }
    return status_map.get(status_code, '未知狀態(tài)')

print(get_status_text(200))  # 成功
print(get_status_text(418))  # 未知狀態(tài)


# 構(gòu)建函數(shù)調(diào)度表
def add(a, b): return a + b
def sub(a, b): return a - b
def mul(a, b): return a * b
def div(a, b): return a / b if b != 0 else None

operations = {
    '+': add,
    '-': sub,
    '*': mul,
    '/': div,
}

def calculate(operator, a, b):
    func = operations.get(operator)
    if func:
        return func(a, b)
    raise ValueError(f'不支持的運(yùn)算符: {operator}')

print(calculate('+', 10, 5))  # 15
print(calculate('*', 10, 5))  # 50

# 字典天然適合做緩存
def memoize(func):
    """裝飾器：為函數(shù)添加緩存"""
    cache = {}
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrapper

@memoize
def fibonacci(n):
    """斐波那契數(shù)列——不帶緩存是O(2^n)，帶緩存是O(n)"""
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# 沒有緩存，fibonacci(40)可能需要幾十秒
# 有了字典緩存，秒出結(jié)果
print(fibonacci(40))  # 102334155