美文网首页
python实现哈希表插入 -- 拉链法

python实现哈希表插入 -- 拉链法

作者: ___大鱼___ | 来源:发表于2019-08-22 16:57 被阅读0次
哈希.png 哈希表.png 哈希冲突.png 解决哈希冲突--开放寻址法.png 解决哈希冲突--拉链法.png
# 链表


class SignLinklist:

    # 节点类
    class Node:
        def __init__(self, item):
            self.item = item
            self.next = None

        def __str__(self):
            return str(self.item)

    # 可迭代链表类
    class LinklistIterator:
        def __init__(self, node):
            self.node = node

        def __next__(self):
            if self.node:
                cur_node = self.node
                self.node = cur_node.next
                return cur_node.item
            else:
                raise StopIteration

        def __iter__(self):
            return self

    def __init__(self, iterable=None):
        self.head = None
        self.tail = None
        if iterable:
            self.extend(iterable)

    # 添加节点
    def append(self, obj):
        node = SignLinklist.Node(obj)
        if not self.head:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    # 批量添加节点
    def extend(self, iterable):
        for obj in iterable:
            self.append(obj)

    # 查找节点
    def find(self, obj):
        for n in self:
            if n == obj:
                return True
        else:
            return False

    # 遍历链表
    def __iter__(self):
        return self.LinklistIterator(self.head)

    # print 调用打印链表
    def __repr__(self):
        return '<<' + ','.join(map(str, self)) + '>>'


# 哈希表 类似于集合
class HashTable:

    def __init__(self, size=100):
        self.size = size
        self.T = [SignLinklist() for x in range(self.size)]

    def h(self, k):
        return k % self.size

    def insert(self, k):
        i = self.h(k)
        if self.find(k):
            print('Duplicated Insert')
        else:
            self.T[i].append(k)

    def find(self, k):
        i = self.h(k)
        return self.T[i].find(k)


if __name__ == '__main__':
    ht = HashTable()
    ht.insert(10)
    ht.insert(110)
    ht.insert(210)
    ht.insert(310)
    print(','.join(map(str, ht.T)))

    print(ht.find(210))


个人博客

相关文章

  • python实现哈希表插入 -- 拉链法

    个人博客

  • HashMap面试基础

    HashMap 必备知识——哈希表 哈希表 哈希函数 哈希碰撞 解决办法 1. 拉链法 2. 线性探测法 Hash...

  • iOS学习笔记(8-26)

    NSDictionary 1、底层是哈希表+拉链法2、对_CFDictionary的封装3、字典的hash实现非常...

  • HashMap若干问题

    HashMap就是一个散列表,它是通过“拉链法”解决哈希冲突的。 1. 哈希表-拉链法 2. HashMap的存取...

  • HashMap源码解析

    1. 简介 HashMap Java中的HashMap是符号表的一种哈希实现(采用拉链法),HashMap用来存储...

  • (1) 面试

    哈希算法处理冲突的机制: 1.开放寻址法2. 再散列法3. 链地址法(拉链法)4. 建立一个公共溢出区参考:哈希表...

  • golang map

    Go 语言中使用拉链法来解决哈希碰撞的问题实现了哈希表,访问、写入和删除等操作都在编译期间被转换成了对应的运行时函...

  • Python算法教程第二章知识点:计时模块、字典与散哈希表、图与

    Python算法教程第二章知识点:计时模块、字典与散哈希表、图与树的实现、成员查询、插入对象

  • JavaScript 数据结构之哈希表(散列表)

    一、 哈希表的介绍 1. 哈希表的优势 哈希表通常是基于数组实现的,但相对于数组,它有很多优势 快速的插入、删除、...

  • NSDictionary相关

    1、GNUStep版本的哈希表,解决冲突的方式是拉链法(源码见GSIMap,结构是map->bucket->nod...

网友评论

      本文标题:python实现哈希表插入 -- 拉链法

      本文链接:https://www.haomeiwen.com/subject/zwxosctx.html