算法介绍（直接寻址表、hash，MD5，贪心算法、动态规划）

直接寻址表

  • 直接寻址表，定义了一个所有关键字的域集合U，根据这个U生成一个包含所有域值的列表T
  • 直接寻址技术优点：
    • 当数据量较小时，相对简单有效
  • 直接寻址技术缺点：
    • 当U很大时，建立列表T，所消耗的内存空间非常大
    • 如果U非常大，而实际出现的key非常少，这样就对空间造成了极大的浪费
    • 当关键字key不是数字的时候就无法处理了

hash（哈希）

  • 基本概念：hash，也称作散列、杂凑或者哈希，是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成，哈希函数h（）将元素的关键字k处理得到唯一的存储元素的位置信息。能把任意长度的输入，通过hash算法转化为固定长度的输出，是一种压缩映射。最大的特点就是从无法从结果推算出输入内容，所以称之为不可逆算法。本质上是通过哈希函数计算数据存储位置的数据结构。
  • hash表示对直接寻址表的改进，具体的
    • 构建大小为m的寻址表T，[0,1,2,3,……,m-1]
    • 将关键字为k的元素，放置在T中的h（k）所指定的位置上
    • h() 是哈希函数，将U中的key映射到寻址表T中
  • 哈希特性：
    • 过程不可逆，即拿到结果也不能反解出输入值是多少
    • 计算速度极快
  • 哈希表存在的问题：
    • 哈希冲突
      • 由于关键字的数量是无限的，而hash创建的寻址表T是有限的，所以必定会出现存储位置冲突或重复，即当h（k）和h（k1）的值相同时，两个值的存储位置是冲突的。
      • 哈希冲突的解决方式：
        • 方式一：开放寻址法，如果哈希函数返回的位置已经有值，则继续向后探寻新的位置来存储这个值。而继续向下探寻位置的方法有
          • 线性探查，如果位置i被占用，则向下探查i+1,i+2 ……直至空位置
          • 二次探查，如果位置i被占用，则依次探查i+1^2，i+2^2……直至空位置
          • 二度哈希：有n个哈希函数，等使用第一个哈希函数h1，发生冲突时，依次尝试使用h2,h3……
        • 方式二：拉链法，哈希表每个位置都链接一个链表，当冲突发生时，冲突的元素被加到该位置链表后面
  • 常见的哈希函数：
    • 除法哈希：  h(k)=k%m
    • 乘法哈希：h(k) = floor(m*(A*key%1))   
    • 全域哈希：h(k) = ((a*key+b) mod p) mod m    a,b =1,2,……p-1
  • hash表的基本操作：
    • insert(key,value) 插入键值对
    • get(key) 根据键取值
    • delete(key)  删除键值对
  • 主要的应用方向：
    • python等语言的字典、集合等数据类型就是基于hash实现的
    • 密码，很多密码都是基于hash构造出来的
    • 可以用于检测文件的一致性
    • 用于数字签名
    • MD5，SHA-1，SHA-2
  • hash表的简单实现（拉链法，单链表） 
    •   1 """
  2 使用链表，实现hash。构建一个类似于集合的hash表
  3 """
  4 class LinkList(object):
  5     """
  6     对链表的进一步封装
  7     """
  8     class Node(object):
  9         """
 10         链表的节点类
 11         """
 12         def __init__(self,item):
 13             self.item = item
 14             self.next = None
 15 
 16     class LinkListIterator(object):
 17         """
 18         将链表转为迭代器类
 19         """
 20         def __init__(self,node):
 21             self.node = node
 22 
 23         def __next__(self):
 24             if self.node:
 25                 cur_node = self.node
 26                 self.node = cur_node.next
 27                 return cur_node.item
 28             else:
 29                 raise StopIteration
 30 
 31         def __iter__(self):
 32             return self
 33 
 34     def __init__(self,iterable = None):
 35         self.head = None
 36         self.tail = None
 37         if iterable:
 38             self.extend(iterable)
 39 
 40     def extend(self,iterable):
 41         for obj in iterable:
 42             self.append(obj)
 43 
 44     def append(self,obj):
 45         """
 46         使用尾插法，进行插入
 47         :param obj:
 48         :return:
 49         """
 50         s = LinkList.Node(obj)  # 链表节点创建
 51         if not self.head:
 52             self.head = s
 53             self.tail = s
 54         else:
 55             self.tail.next = s
 56             self.tail = s
 57 
 58     def find(self,obj):
 59         for val in self:
 60             if val == obj:
 61                 return True
 62         else:
 63             return False
 64 
 65     def __iter__(self):
 66         return self.LinkListIterator(self.head)
 67 
 68     def __repr__(self):
 69         return "<<"+",".join(map(str,self)) +">>"
 70 
 71 
 72 class HashTable(object):
 73     """
 74     实现集合的部分功能，不可重复，可查询
 75     """
 76     def __init__(self,size=101):
 77         self.size = size
 78         self.T = [LinkList() for _ in range(self.size)]  # 创建寻址表
 79 
 80     def h_func(self,k):
 81         """
 82         哈希函数
 83         :param k:
 84         :return:
 85         """
 86         return k%self.size
 87 
 88     def find(self,k):
 89         """
 90         根据给定的k值在现有的范围中查找是否存在
 91         :param k:
 92         :return:
 93         """
 94         hash_num = self.h_func(k) # 获取给定数值的hash值
 95         return self.T[hash_num].find(k)
 96 
 97 
 98     def insert(self,k):
 99         """
100         实现插入前去重
101         :param k:
102         :return:
103         """
104         if self.find(k):
105             print('element is exist')
106         else:
107             hash_num = self.h_func(k)  # 获取插入的值的hash值
108             self.T[hash_num].append(k)
109 
110 
111 my_set = HashTable()
112 my_set.insert(1)
113 my_set.insert(2)
114 my_set.insert(102)
115 print(my_set.T)
116 print(my_set.find(2))
      View Code

  • Python中hash的使用，通过调用hashlib模块实现

    • 通过hashlib调用不同的hash函数，实现不同数据的不同处理。

      • 实例化hash对象，hash_obj = hash.hash函数类型（）   ，实例化过程中，可以通过添加参数，实现加盐操作

      • 常见的hash函数类型有md5，sha1，sha224，sha256，sha384，sha512等 

      • hash_obj.update( 处理内容 ) 注意，需要进行处理的内容必须是bytes类型
      • hash_obj.digest()  ，返回当前已处理内容的hash值（内容摘要），返回值二进制数据
      • hash_obj.hexdigest()，返回当前已处理内容的hash值（内容摘要），返回值是十六进制数据

　　

 MD5

  • 曾是密码学中常用的hash函数
  • 主要特点：
    • 同样的消息MD5相同
    • 可以快速计算出任意长度的消息的MD5
    • 除非暴力美剧，否则基本不能从哈希值反推出消息本身
    • 两条消息之间，即使是只有微笑差别，其MD5应该是完全不同，不相关的
    • 在有限时间内，无法人工构建出MD5值相同的两个不同的信息
  • 应用举例：
    • 验证文件，例如是否是相同的文件，上传下载文件的完整性、云盘秒传等

 SHA-1，SHA-2

  • SHA-1和MD5都是曾经在密码学上经常用到的hash算法，但是目前，较为常用的是SHA-2
  • SHA-2算法包含，SHA-224，SHA-256,SHA-384，SHA-512，SHA-512/224，SHA-512/256等算法，穷224,256,384与512代表的是哈希值的长度

贪心算法

  • 贪心算法也叫做贪婪算法，基本思路是在求解过程中，只考虑当前步骤的最优选择，不从整体上进行考虑。贪心算法重点是放在了求解局部最优解，但是，很多情况下，贪心算法执行出来的结果也是整体上的最优解。
  • 特点：解决的是部分最优化问题
  • 实例：
    • 找零问题
    • 背包问题
    • 数字拼接问题
    • 活动选择问题

动态规划

  • 动态规划关键点是找到关系到最优子结构的递推式，最优子结构
  • 最优子结构，如果可以将最优解的规模为n的问题，划分为规模更小的最优解问题，这些子问题是独立求解的，通过组合子问题的最优解可以得到原整体问题的最优解，就可以称之为最优子结构。
  • 动态规划特征
    • 最优子结构，最优解问题中，原问题的最优解中涉及到多个子问题
    • 重叠子问题
  • 实例：
    • 钢条切割问题
    • 最长公共子序列
      • 子序列与子串，子序列是在某个序列中删除若干元素后得到的序列，与子串的区别是，子序列的元素在原序列中，不一定是相邻的，而子串的元素在原序列中一定是相邻的
      • 应用场景
        • 字符串相似度（模糊查询）
        • 内容相似比对
        • 基因测序等

　　

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/shengjie1/p/11057016.html