理解哈希映射的负载因子

# 1. 简介

## 1.1 什么是哈希映射？

哈希映射是一种数据结构，也称为哈希表，它通过将键（key）映射到值（value）的方式来存储元素。在哈希映射中，每个键都唯一对应一个值，这样可以快速地通过键来查找对应的值。

## 1.2 哈希映射的作用

哈希映射被广泛应用于计算机科学领域，用于存储和快速查找数据。它可以在常数时间复杂度内实现数据的插入、查找和删除操作，因此在大多数情况下，哈希表都能提供高效的数据操作。

## 1.3 负载因子的定义和作用

负载因子（Load Factor）是指哈希表中已存储元素数量与哈希表大小的比值。负载因子的作用是衡量哈希表的空间利用率，通常通过调整负载因子的大小可以影响哈希表的性能和空间利用情况。

# 2. 哈希表的基本原理

哈希表是一种用于存储键值对的数据结构，通过哈希函数将键映射到存储位置，以实现快速的插入、删除和查找操作。

### 2.1 哈希函数

哈希函数用于将键映射到哈希表的索引位置。它接受一个键作为输入，并返回一个对应的哈希值。好的哈希函数应该满足以下特点：

- 一致性：相同的输入键应该始终映射到相同的哈希值。
- 均匀性：哈希函数应该将键均匀地映射到哈希表的不同索引位置，以减少冲突的发生。

常见的哈希函数有求余数法、乘法法和位运算法等。

### 2.2 冲突处理

由于哈希函数的映射空间通常比键的实际范围要小，不同的键可能会映射到相同的索引位置，导致冲突的发生。哈希表通常采用以下两种方法来处理冲突：

- 链地址法：每个哈希表的索引位置维护一个链表，在发生冲突时，将键值对添加到对应链表的末尾。
- 开放地址法：在发生冲突时，使用特定的算法找到哈希表的下一个可用位置，称为探查。

### 2.3 哈希表的实现

哈希表可以用数组实现，数组的索引位置即为哈希值，数组的每个元素存储一个链表或者键值对。

class HashMap:
    def __init__(self):
        self.size = 16  # 哈希表的大小
        self.table = [None] * self.size  # 哈希表的数组

    def hash_function(self, key):
        return key % self.size  # 求余数法作为哈希函数

    def put(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]  # 创建新的链表并存储键值对
        else:
            for pair in self.table[index]:
                if pair[0] == key:
                    pair[1] = value  # 如果键已存在，则更新对应的值
                    return
            self.table[index].append((key, value))  # 否则，在链表末尾插入新的键值对

    def get(self, key):
        index = self.hash_function(key)
        if self.table[index] is not None:
            for pair in self.table[index]: