hash_table_app.py

"""
哈希表应用模块
Hash Table Application Module
"""

from graph_storage import SocialNetwork


class HashTable:
    """
    哈希表实现，用于快速查询
    Hash Table implementation for fast queries
    
    哈希函数采用除法散列，冲突解决使用链地址法
    Hash function uses division method, collision resolution uses chaining
    """
    
    def __init__(self, size=1000):
        """
        初始化哈希表
        Initialize hash table
        
        Args:
            size (int): 哈希表大小 Hash table size
        """
        self.size = size
        self.table = [[] for _ in range(size)]  # 使用链地址法处理冲突 Use chaining to handle collisions
        self.count = 0  # 元素数量 Number of elements
    
    def _hash(self, key):
        """
        哈希函数
        Hash function
        
        Args:
            key: 键 Key
            
        Returns:
            int: 哈希值 Hash value
        """
        if isinstance(key, str):
            # 字符串哈希：使用多项式滚动哈希 Use polynomial rolling hash for strings
            hash_value = 0
            for char in key:
                hash_value = (hash_value * 31 + ord(char)) % self.size
            return hash_value
        else:
            # 数字哈希：使用除法散列 Use division hashing for numbers
            return hash(key) % self.size
    
    def insert(self, key, value):
        """
        插入键值对
        Insert key-value pair
        
        Args:
            key: 键 Key
            value: 值 Value
        """
        index = self._hash(key)
        bucket = self.table[index]
        
        # 检查键是否已存在 Check if key already exists
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新现有键 Update existing key
                return
        
        # 添加新的键值对 Add new key-value pair
        bucket.append((key, value))
        self.count += 1
    
    def search(self, key):
        """
        搜索键对应的值
        Search for value corresponding to key
        
        Args:
            key: 键 Key
            
        Returns:
            值或None Value or None if not found
        """
        index = self._hash(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return None  # 未找到 Not found
    
    def delete(self, key):
        """
        删除键值对
        Delete key-value pair
        
        Args:
            key: 键 Key
            
        Returns:
            bool: 是否删除成功 Whether deletion was successful
        """
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.count -= 1
                return True
        
        return False  # 键不存在 Key doesn't exist


class HashOptimizedNetwork(SocialNetwork):
    """
    使用哈希表优化的社交网络类
    Social Network class optimized with hash tables
    """
    
    def __init__(self, n, directed=True, storage_type="adj_list"):
        super().__init__(n, directed, storage_type)
        
        # 创建哈希表用于快速查询 Create hash tables for fast queries
        self.user_info_table = HashTable(size=max(1000, n // 10))  # 用户信息表 User info table
        self.edge_query_table = HashTable(size=max(2000, n // 5))   # 边查询表 Edge query table
        self.label_query_table = HashTable(size=max(1000, n // 10)) # 标签查询表 Label query table
        
        # 初始化用户信息表 Initialize user info table
        for i in range(n):
            self.user_info_table.insert(i, self.user_attributes[i])
    
    def add_edge(self, u, v):
        """
        添加关注关系（重写父类方法以更新哈希表）
        Add following relationship (override parent method to update hash tables)
        """
        super().add_edge(u, v)
        
        # 更新用户信息表 Update user info table
        self.user_info_table.insert(u, self.user_attributes[u])
        self.user_info_table.insert(v, self.user_attributes[v])
        
        # 更新边查询表 Update edge query table
        edge_key = (u, v)
        self.edge_query_table.insert(edge_key, True)
    
    def remove_edge(self, u, v):
        """
        移除关注关系（重写父类方法以更新哈希表）
        Remove following relationship (override parent method to update hash tables)
        """
        super().remove_edge(u, v)
        
        # 更新用户信息表 Update user info table
        self.user_info_table.insert(u, self.user_attributes[u])
        self.user_info_table.insert(v, self.user_attributes[v])
        
        # 更新边查询表 Update edge query table
        edge_key = (u, v)
        self.edge_query_table.delete(edge_key)
    
    def quick_user_lookup(self, user_id):
        """
        快速用户信息查询
        Quick user information lookup
        
        Args:
            user_id (int): 用户ID User ID
            
        Returns:
            dict: 用户信息 User information
        """
        return self.user_info_table.search(user_id)
    
    def quick_edge_check(self, u, v):
        """
        快速检查两个用户之间是否存在关注关系
        Quickly check if there's a following relationship between two users
        
        Args:
            u (int): 起始用户ID Start user ID
            v (int): 目标用户ID Target user ID
            
        Returns:
            bool: 是否存在关注关系 Whether following relationship exists
        """
        edge_key = (u, v)
        result = self.edge_query_table.search(edge_key)
        return result is not None
    
    def quick_label_search(self, label):
        """
        快速检索具有相同标签的用户
        Quickly retrieve users with the same label
        
        Args:
            label: 标签 Label
            
        Returns:
            list: 具有相同标签的用户列表 List of users with the same label
        """
        # 遍历所有用户来查找具有特定标签的用户
        # Iterate through all users to find those with specific label
        users_with_label = []
        for user_id in range(self.n):
            user_info = self.quick_user_lookup(user_id)
            if user_info and user_info.get('label') == label:
                users_with_label.append(user_id)
        
        return users_with_label


# 测试示例
if __name__ == "__main__":
    print("哈希表应用 - 示例运行")
    print("Hash Table Application - Example Run")
    
    # 创建一个哈希优化的网络 Create a hash-optimized network
    network = HashOptimizedNetwork(5, directed=True, storage_type="adj_list")
    
    # 添加一些边 Add some edges
    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
    for u, v in edges:
        network.add_edge(u, v)
    
    print(f"添加了 {len(edges)} 条边")
    print(f"Added {len(edges)} edges")
    
    # 测试快速用户查询 Test quick user lookup
    user_info = network.quick_user_lookup(3)
    print(f"用户3的信息: {user_info}")
    print(f"User 3 info: {user_info}")
    
    # 测试快速边查询 Test quick edge check
    edge_exists = network.quick_edge_check(0, 1)
    print(f"用户0到用户1的边是否存在: {edge_exists}")
    print(f"Edge from user 0 to user 1 exists: {edge_exists}")
    
    edge_exists = network.quick_edge_check(1, 0)
    print(f"用户1到用户0的边是否存在: {edge_exists}")
    print(f"Edge from user 1 to user 0 exists: {edge_exists}")
    
    # 测试标签搜索 Test label search
    users_with_label_0 = network.quick_label_search(0)
    print(f"标签为0的用户: {users_with_label_0}")
    print(f"Users with label 0: {users_with_label_0}")
    
    # 测试哈希表的基本操作 Test basic hash table operations
    print(f"\n测试哈希表基本操作...")
    print(f"Testing basic hash table operations...")
    
    ht = HashTable(size=10)
    
    # 插入操作 Insert operations
    ht.insert("name", "Alice")
    ht.insert("age", 25)
    ht.insert("city", "Beijing")
    
    print(f"姓名: {ht.search('name')}")  # Name
    print(f"Age: {ht.search('age')}")   # Age
    print(f"城市: {ht.search('city')}")  # City
    
    # 更新操作 Update operation
    ht.insert("age", 26)
    print(f"更新后的年龄: {ht.search('age')}")  # Updated age
    print(f"Updated age: {ht.search('age')}")
    
    # 删除操作 Delete operation
    deleted = ht.delete("city")
    print(f"删除城市结果: {deleted}")  # Delete city result
    print(f"Delete city result: {deleted}")
    print(f"删除后城市查询: {ht.search('city')}")  # Query city after deletion
    print(f"Query city after deletion: {ht.search('city')}")