python实现顺序查找和哈希查找算法-阿里云开发者社区

开发者社区> python之战> 正文

python实现顺序查找和哈希查找算法

简介: 顺序查找 顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法,顺序查找是最简单的搜索算法,其实现如下: def sequential_search(items, item):     for i in items:         if i == item:             return i     else:         return False 适用于线性表的顺序存储结构和链式存储结构,该算法的时间复杂度为O(n)。
+关注继续查看

顺序查找

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法,顺序查找是最简单的搜索算法,其实现如下:

def sequential_search(items, item):
    for i in items:
        if i == item:
            return i
    else:
        return False


适用于线性表的顺序存储结构和链式存储结构,该算法的时间复杂度为O(n)

缺点:是当n 很大时,平均查找长度较大,效率低;

   优点:是对表中数据元素的存储没有要求。另外,对于线性链表,只能进行顺序查找。

哈希查找算法

哈希查找算法,依赖哈希表这种数据结构,它是以键值对的形式存储数据,对于哈希查找算法来说,其时间复杂度为O(1),Redis数据表中也有哈希存储,储存形式是键值对。

python实现哈希数据结构及其哈希查找算法:

class HashTable:
    def __init__(self, size):
        self.elem = [None for i in range(size)]  # 使用list数据结构作为哈希表元素保存方法
        self.count = size  # 最大表长

    def hash(self, key):
        return key % self.count  # 散列函数采用除留余数法

    def insert_hash(self, key):
        """插入关键字到哈希表内"""
        address = self.hash(key)  # 求散列地址
        while self.elem[address]:  # 当前位置已经有数据了,发生冲突。
            address = (address + 1) % self.count  # 线性探测下一地址是否可用
        self.elem[address] = key  # 没有冲突则直接保存。

    def search_hash(self, key):
        """查找关键字,返回布尔值"""
        star = address = self.hash(key)
        while self.elem[address] != key:
            address = (address + 1) % self.count
            if not self.elem[address] or address == star:  # 说明没找到或者循环到了开始的位置
                return False
        return True

源码来自:https://www.cnblogs.com/lsqin/p/9342929.html

哈希查找的产生有这样一种背景——有些数据本身是无法排序的(如图像),有些数据是很难比较的(如图像)。如果数据本身是无法排序的,就不能对它们进行比较查找。

如果数据是很难比较的,即使采用折半查找,要比较的次数也是非常多的。因此,哈希查找并不查找数据本身,而是先将数据映射为一个整数(它的哈希值),并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。

在哈希查找的过程中,只需先将要查找的数据映射为它的哈希值,然后查找具有这个哈希值的数据,这就大大减少了查找次数。

如果构造哈希函数的参数经过精心设计,内存空间也足以存放哈希表,查找一个数据元素所需的比较次数基本上就接近于一次。


2019-04-21-23_24_56.png


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
一文详解神经网络 BP 算法原理及 Python 实现
  什么是梯度下降和链式求导法则 假设我们有一个函数 J(w),如下图所示。 梯度下降示意图 现在,我们要求当 w 等于什么的时候,J(w) 能够取到最小值。从图中我们知道最小值在初始位置的左边,也就意味着如果想要使 J(w) 最小,w的值需要减小。
2699 0
一致性哈希算法的php实现与分析-算法
<?php/** 一致性哈希算法* 过程:* 1,抽象一个圆,然后把服务器节点按一定算法得到整数有序顺时针放到圆上,圆环用2^32 个点来进行均匀切割。* hash函数的结果应该均匀分布在[0,2^32-1]区间* 2,由于服务器少,在圆上分布不均匀会造成数据倾斜,所以我们使用虚拟节点代替服务器的节点,一个服务器生成32个虚拟节点,或者更多。
1373 0
数据结构和算法对python意味着什么?
数据结构和算法对于python而言是他的灵魂;程序是数据结构加上算法来实现的,对于任何一门编程语言都离不开数据结构和算法,但是对于python而言内置了基础的数据结构如列表、字典、集合等,再加上众多包,所以弱化了数据结构和算法的使用。
1733 0
一致性哈希算法应用与分析
  一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。感觉一致性哈希与数据结构中的“循环队列”还是有一点联系的。
770 0
python实现DES加密算法和3DES加密算法
pyDes.py ############################################################################# # Documentation # #####...
1605 0
谷歌百度以图搜图 "感知哈希算法" C#简单实现
/// /// 感知哈希算法 /// public class ImageComparer { /// /// 获取图片的Hashcode /// /// /// public static string GetImageHashCode(string imageName) { int width = 8; int height = 8; // 第一步 // 将图片缩小到8x8的尺寸,总共64个像素。
1620 0
查找类算法之二分搜索树 | 算法必看系列十
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
559 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载