关于android:数据结构Hash常见操作实践

1次阅读

共计 8746 个字符，预计需要花费 22 分钟才能阅读完成。

数据结构 -Hash 常见操作实际

目录介绍
  • 01. 什么是哈希算法
  • 02. 哈希算法的利用
  • 03. 平安加密的场景
  • 04. 惟一标识的场景
  • 05. 数据校验的场景
  • 06. 散列函数的场景
  • 07.Git 版本的管制
  • 08. 云存储文件场景
  • 09. 哈希算法的总结
  • 10. 哈希算法的特点
  • 11. 哈希算法的实际
  • 12. 罕用哈希码算法
  • 13.Map 哈希的算法
  • 14. 了解 HashCode
  • 15. 哈希抵触的解决
  • 16. 问题思考的答疑

01. 什么是哈希算法

  • 哈希算法历史悠久

    • 业界驰名的哈希算法也很多，比方 MD5、SHA 等。在平时的开发中，基本上都是拿现成的间接用。明天不会重点分析哈希算法的原理，也不会教你如何设计一个哈希算法，而是从实战角度通知你，在理论开发中，咱们该如何用哈希算法解决问题。

  • 什么是哈希算法，用一句话就能够概括了。

    • 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射规定就是哈希算法，而通过原始数据映射之后失去的二进制值串就是哈希值。

  • 然而，要设计一个优良的哈希算法并不容易，我了须要满足的几点要求：

    • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
    • 对输出数据十分敏感，哪怕原始数据只批改了一个 Bit，最初失去的哈希值也大不相同；
    • 散列总被的概率要很小，对于不同的原始数据，哈希值雷同的概率十分小；
    • 哈希算法的执行效率尽量高效，针对较长的文本，也能疾速计算出哈希值。

  • 拿 MD5 这种哈希算法具体阐明下，比方计算这两个文本的 MD5 哈希值——“明天我来讲哈希算法”、“jiajia”。失去的两串毫无法则的字符串（MD5 的哈希值是 128 位的 Bit 长度，便于示意，转化为 16 进制编码）。能够看出，无论文本的长度是多少，失去的哈希值长度是雷同的，而且看起来像一堆随机数，齐全没有法则。

    MD5("明天我来讲哈希算法") = bb4767201ad42c74e650c1b6c03d78fa
MD5("jiajia") = cd611a31ea969b908932d44d126d195b

  • 试试两个很类似的文本，尽管只有一个标点的差异，但哈希值是齐全不雷同的。同时依据哈希值，是很难反向推导出原始数据。

    MD5("我明天讲哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb
MD5("我明天讲哈希算法")  = a1fb91ac128e6aa37fe42c663971ac3d

  • 哈希算法要解决的文本可能是各种各样的。

    • 比方，对于十分长的文本，如果哈希算法的计算工夫很长，那就只能停留在实践钻研的层面，很难利用到理论软件开发中。
    • 比方，把明天的这篇蕴含 4000 多个汉字的文章，用 MD5 计算哈希值，用不了 1ms 的工夫。

02. 哈希算法的利用

  • Hash 有哪些风行的算法

    • 目前风行的 Hash 算法包含 MD5、SHA-1 和 SHA-2。

  • 哈希算法次要有哪些

    • MD5 算法：MD5，MD5+ 盐
    • SHA 算法：蕴含 5 个算法，别离是 SHA-1、SHA-224、SHA-256、SHA-384 和 SHA-512，后四者并称为 SHA-2。

  • 哈希算法的利用十分十分多，选了最觉的七个

    • 别离是平安加密、惟一标识、数据校验、散列函数、Git 版本控制、云存储、数据分片。

03. 平安加密的场景

  • 说到哈希算法的利用，最先想到的应该是平安加密。

    • 最罕用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 音讯摘要算法）和 SHA（Secure Hash Algorithm，平安散列算法）。除了这两个之外，当然还有很多其余的加密办法，比方 DES（Advance Encryption Standard，高级加密规范）。

  • 对用于加密的哈希算法来说，有两点很重要：第一是很难依据哈希值反向推导出原始数据，第二是散列抵触的概率要很小。

    • 第一点很好了解，加密的目标就是不会悔恨原始数据泄露，所以很难通过哈希值反向推导出原始以数据，这是一个根本要求。
    • 重点说说第二点，但不论什么哈希算法，咱们只能尽量减少碰撞抵触的概率，实践上是没方法做到齐全不抵触的，这是为什么呢？

  • 基于组合数学中一个叛党根底的实践，鸽巢原理（也叫抽屉原理）。

    • 这个原理自身很简略，它是说，如果有 10 个鸽巢，有 11 只鸽子，那必定有 1 个鸽巢中的鸽子数量大于 1，换句话说就是，必定有一个巢里的鸽子数量大于 1。
    • 哈希算法产生的哈希值的长度是固定且无限的。比方后面说的 MD5 的鸽子，哈希值是固定的 128 位二进制串，能示意的数据是无限的，最多示意 2^128 个数据，而咱们要哈希的数据能够是无穷的，那必然会存在哈希值雷同的状况。
    • 如果咱们拿到一个 MD5 哈希值，心愿通过毫无法则的穷举的办法，找到这个 MD5 值雷同的另一个数据，那消耗的工夫应该是个天文数字了。即使哈希算法实践上存在抵触，但还是很难破解的。

  • 除此之外，没有相对平安的加密。

    • 越简单、越难破解的加密算法，须要的计算工夫也越长。比方 SHA-256 比 SHA- 1 要更简单、更平安，相应的计算工夫就会比拟长。

04. 惟一标识的场景

  • 先举个例子。如果要在海量的图库中，搜寻一张图是否存在，咱们不能单纯地用图片的元信息（比方图片名称）来比照，因为有可能存在名称雷同但图片内容不同，或者名称不同图片内容雷同的状况。那咱们该如何搜寻呢？

    • 任何文件在计算机中都能够示意成二进制码串，所以，比拟笨的方法就是，拿要查找的图片的二进制码串与图库中所有图片的二进制码串逐个比对。如果雷同，则阐明图片在图库中存在。
    • 然而，每个图片小则几十 KB、大则几 MB, 转化成二进制是一个十分长的串，比对起来十分耗时。有没有比拟快的办法呢？

  • 能够给每一个图片取一个惟一标识，或者说信息摘要。

    • 比方，咱们能够从图片二进制码串开关取 100 个字节，从两头取 100 个字节，从最初取 100 个字节，而后将这 300 个字节放一块。通过这个惟一标识来断定图片是否在图库中，这样就能够缩小很多工作量。

  • 如果还想持续提高效率，咱们能够把每个图片的惟一标识，和相应的图片文件在图库中的门路信息，都存储在散列表中。

    • 当要查看某个图片是不是在图库的时候，咱们先通过哈希算法对这个图片取惟一标识，而后在散列表中查找是否存在这个标识。
    • 如果不存在，那就阐明这个图片不在图库中，如果存在，咱们再通过散列表存储的文件门路，获取到这个曾经存在的图片，跟当初要插入的图片做全量的比对，看是否齐全一样，如果一样，就阐明曾经存在；如果一一样，阐明两张图片只管惟一标识雷同，然而并不是雷同的图片。

05. 数据校验的场景

  • 电驴这样的 BT 下载软件听过吧！BT 下载的原理是基石地 P2P 协定的。

    • 咱们从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被宰割成很多文件块（比方能够分成 100 块，每块大概 200MB）。等所有的文件块都下载实现之后，再组装成一个残缺的电影文件就行了。
    • 网络传输是不平安的，下载的文件块有可能是被宿主机歹意批改过的，又或者下载过程中呈现了谬误，所以下载的文件块可能不是残缺的。如果咱们没有能力检测这种歹意批改或者文件下载出错，就会导致最终合并后的电影无奈观看，甚至导致电脑中毒。当初的问题是，如何来校验文件块的平安、正确、残缺呢？

  • 具体的 BT 协定很简单，校验办法也有很多，我来说其中的一种思路。

    • 咱们通过哈希算法，对 100 个文件块别离取哈希值，并且保留种子文件中。在后面讲过，哈希算法有一个特点，对数据很敏感。只有文件块内容有一丁点儿的扭转，最初计算出的哈希值就会齐全不同。
    • 所以，当文件块下载实现之后，咱们能够通过雷同的哈希算法，对下载好的文件逐个求哈希值，而后跟种子文件中保留的哈希值比对。如果不同，阐明这个文件块不残缺或者被篡改了，须要再从新从其余宿主机上下载这个文件块。

06. 散列函数的场景

  • 散列函数是设计一个散列表的要害。

    • 它间接决定了散列抵触的概率和散列表的性能。不过，绝对哈希算法的其余利用，散列函数对于散列算法抵触的要求要低很多。即使是呈现个别散列抵触，只有不是过于重大，咱们都能够通过凋谢寻址法或者链表法解决。
    • 不仅如此，散列函数对于散列算法计算失去的值，是否能反向解密也并不关怀。散列函数中用到的散列算法，更加关注散列后的值是否能均匀散布，也就是，一组数据是否能平均的散列到各个槽中。
    • 除此之外，散列函数执行的快慢，也会影响散列表的性能，能以，散列函数用的散列算法个别都比较简单，比拟谋求效率。

  • 最常见的散列函数利用场景

    • 比方工业存储 key-value 汇合 HashMap 数据结构，存储 key 就用到了散列函数！

  • HashMap 为何对 key 应用哈希算法

    • hash 值（key）存在的目标是减速键值对的查找，key 的作用是为了将元素适当地放在各个桶里，对于抗碰撞的要求没有那么高。

07.Git 版本的管制

  • 以 Git 为代表的泛滥版本控制工具都在应用 SHA1 等散列函数查看文件更新

    • 包含 GitHub 在内的泛滥版本控制工具以及各种云同步服务都是用 SHA1 来区别文件，很多平安证书或是签名也应用 SHA1 来保障唯一性。
    • 长期以来，人们都认为 SHA1 是非常平安的，至多大家还没有找到一次碰撞案例。

08. 云存储文件场景

  • 当初大部分的网络部署和版本控制工具都在应用散列算法来保障文件可靠性。

    • 在进行文件系统同步、备份等工具时，应用散列算法来标记文件惟一性能帮忙咱们缩小零碎开销，这一点在很多云存储服务器中都有利用。
    • 当原有文件产生扭转时，其标记值也会产生扭转，从而通知文件使用者以后的文件曾经不是你所需要的文件。

  • 散列函数很难可逆

    • 这种不可逆性体现在，你不仅不可能依据一段通过散列算法失去的指纹来取得原有的文件，也不可能简略地发明一个文件并让它的指纹与一段指标指纹相一致。

09. 哈希算法的总结

  • 第一个利用是惟一标识，哈希算法能够对大数据做信息摘要，通过一个较短的二进制编码来示意很大的数据。
  • 第二个利用是校验数据的完整性和正确性。
  • 第三个利用是平安加密，任何哈希算法都会呈现散列抵触，然而这个抵触的概率十分小。越是简单的哈希算法越难破解，但同样计算工夫也就越长。所以，抉择哈希算法的时候，要衡量安全性和计算工夫来决定用哪种哈希算法。
  • 第四个利用是散列函数，这个咱们后面讲散列表的时候具体说过，它对哈希算法的要求十分特地，更加看重的是散列的均匀性和哈希算法的执行效率。

10. 哈希算法的特点

  • 正向疾速：

    • 给定明文和 hash 算法，在无限工夫和无限资源内能计算出 hash 值。

  • 逆向艰难：

    • 给定（若干）hash 值，在无限工夫内很难（根本不可能）逆推出明文。

  • 输出敏感：

    • 原始输出信息批改一点信息，产生的 hash 值看起来应该都有很大不同。

  • 抵触防止：

    • 很难找到两段内容不同的明文，使得它们的 hash 值统一（发生冲突）。即对于任意两个不同的数据块，其 hash 值雷同的可能性极小；对于一个给定的数据块，找到和它 hash 值雷同的数据块极为艰难。

11. 哈希算法的实际

  • 提供几个简略的概念供大家参考

    • 作为散列算法，首要的性能就是要应用一种算法把原有的体积很大的文件信息用若干个字符来记录，还要保障每一个字节都会对最终后果产生影响。
    • 那么大家兴许曾经想到了，求模这种算法就能满足咱们的须要。事实上，求模算法作为一种不可逆的计算方法，曾经成为了整个古代密码学的根基。

  • 只有是波及到计算机平安和加密的畛域，都会有模计算的身影。

    • 散列算法也并不例外，一种最原始的散列算法就是单纯地抉择一个数进行模运算，比方以下程序。

      #  结构散列函数
def hash(a):
return a % 8

#  测试散列函数性能
print(hash(233))
print(hash(234))
print(hash(235))
    • 1
    • 2

    • 3

    • 上述的程序实现了一个散列算法所该当实现的高级指标：用较少的文本量代表很长的内容（求模之后的数字必定小于 8）。
    • 但兴许你曾经留神到了，单纯应用求模算法计算之后的后果带有显著的规律性，这种法则将导致算法将能难保障不可逆性。所以咱们将应用另外一种伎俩，那就是异或。

  • 在散列函数中退出一个异或过程

    #  结构散列函数
def hash(a):
    return (a % 8) ^ 5

#  测试散列函数性能
print(hash(233))
print(hash(234))
print(hash(235))

# 输入后果
- 4
- 7
- 6
    • 很显著的，退出一层异或过程之后，计算之后的后果规律性就不是那么显著了。
    • 如果用户应用间断变动的一系列文本与计算结果相比对，就很有可能找到算法所蕴含的法则。

  • 在进行计算之前对原始文本进行批改，或是退出额定的运算过程（如移位）

    #  结构散列函数
def hash(a):
    return (a + 2 + (a << 1)) % 8 ^ 5

#  测试散列函数性能
print(hash(233))
print(hash(234))
print(hash(235))

# 输入后果
- 0
- 5
- 6
    • 这样解决失去的散列算法就很难发现其外部法则

  • 下面的算法是不是很简略？

    • 事实上，罕用算法 MD5 和 SHA1，其本质算法就是这么简略，只不过会退出更多的循环和计算，来增强散列函数的可靠性。

12. 罕用哈希码算法

  • 上面给出在 Java 中几个罕用的哈希码 (hashCode) 的算法。

    • Object 类的 hashCode. 返回对象的通过解决后的内存地址，因为每个对象的内存地址都不一样，所以哈希码也不一样。这个是 native 办法，取决于 JVM 的外部设计，个别是某种 C 地址的偏移。
    • String 类的 hashCode. 依据 String 类蕴含的字符串的内容，依据一种非凡算法返回哈希码，只有字符串的内容雷同，返回的哈希码也雷同。
    • Integer 等包装类，返回的哈希码就是 Integer 对象里所蕴含的那个整数的数值，例如 Integer i1=new Integer(100), i1.hashCode 的值就是 100。由此可见，2 个一样大小的 Integer 对象，返回的哈希码也一样。
    • int，char 这样的根底类，它们不须要 hashCode，如果须要存储时，将进行主动装箱操作，计算方法同上。

13.Map 哈希的算法

  • 对 key 进行 Hash 计算

    • 在 JDK8 中，因为应用了红黑树来解决大的链表开销，所以 hash 这边能够更加省力了，只用计算 hashCode 并挪动到低位就能够了。

      static final int hash(Object key) {
int h;
// 计算 hashCode，并无符号挪动到低位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    • 举个例子: 363771819^(363771819 >>> 16)。这样做能够实现了高位置更加平均地混到一起。

    • 0101 1010 1110 1011 0111 1010 1011(363771819)
    • 0000 0000 0000 0001 0101 1010 1110(5550) XOR
      ————————————— =

    • 0101 1010 1110 1010 0010 0000 0101(363766277)

  • 获取到数组的 index 的地位。计算了 Hash，咱们当初要把它插入数组中了

    //tab：是 Node<K,V>[] tab
int index = (tab.length - 1) & hash;
    • 通过位运算，确定了以后的地位，因为 HashMap 数组的大小总是 2^n，所以理论的运算就是 (0xfff…ff) & hash，这里的 tab.length- 1 相当于一个 mask，滤掉了大于以后长度位的 hash，使每个 i 都能插入到数组中。

    • 这个对象是一个包装类，Node

      static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    //getter and setter .etc.
}

    • 插入包装类到数组。如果输出以后的地位是空的，就插进去，如图，左为插入前，右为插入后

      0           0
|           |
1 -> null   1 - > null
|           |
2 -> null   2 - > null
|           | 
..-> null   ..- > null
|           | 
i -> null   i - > new node
|           |
n -> null   n - > null

    • 如果以后地位曾经有了 node，且它们产生了碰撞，则新的放到后面，旧的放到前面，这叫做链地址法解决抵触。能够发现，失败的 hashCode 算法会导致 HashMap 的性能由数组降落为链表，所以想要防止产生碰撞，就要进步 hashCode 后果的平均性。

      0           0
|           |
1 -> null   1 - > null
|           |
2 -> null   2 - > null
|           | 
..-> null   ..- > null
|           | 
i -> old    i - > new - > old
|           |
n -> null   n - > null

14. 了解 HashCode

  • HashCode 也是哈希算法的一种

    • HashCode 是 Object 的一个办法，hashCode 办法返回一个 hash code 值，且这个办法是为了更好的反对 hash 表，比方 String，Set，HashTable、HashMap 等;

  • HashCode 的意义是什么

    • 如果用 equal 去比拟的话，如果存在 1000 个元素，你 new 一个新的元素进去，须要去调用 1000 次 equal 去一一和他们比拟是否是同一个对象，这样会大大降低效率。
    • hashcode 实际上是返回对象的存储地址，如果这个地位上没有元素，就把元素间接存储在下面，如果这个地位上曾经存在元素，这个时候才去调用 equal 办法与新元素进行比拟，这样大大提高效率。

  • HashCode 的作用

    • 缩小查找次数，进步程序效率。例如查找是否存在反复值
    • h(k1)≠h(k2)则 k1≠k2
    • 首先查看 h(k2)输入值（内存地址），查看该内存地址是否存在值；
    • 如果无，则示意该值不存在反复值；
    • 如果有，则进行值比拟，雷同则示意该值曾经存在散列列表中，如果不雷同则再进行一个一个值比拟；而无需一开始就一个一个值的比拟，缩小了查找次数

  • 用 hashcode 判断两个对象是否相等能够吗

    • 必定是不能够的，因为不同的对象可能会生成雷同的 hashcode 值。尽管不能依据 hashcode 值判断两个对象是否相等，然而能够间接依据 hashcode 值判断两个对象不等，如果两个对象的 hashcode 值不等，则必然是两个不同的对象。如果要判断两个对象是否真正相等，必须通过 equals 办法。

  • 思考一下上面问题

    • 应用 HashMap 存储对象，对 key 进行哈希算法，可能会呈现碰撞，那么如何解决碰撞呢？

15. 哈希抵触的解决

  • 什么是哈希抵触

    • 对不同的关键字可能失去同一散列地址，即 key1≠key2，而 f(key1)=f(key2)，这种景象称 hash 抵触。
    • 即：key1 通过 f(key1)失去散列地址去存储 key1，同理，key2 发现自己对应的散列地址曾经被 key1 占据了。
  • 解决办法（总共有四种）：

  • 1. 凋谢寻址法

    • 所谓的凋谢定址法就是一旦产生了抵触，就去寻找下一个空的散列地址，只有散列表足够大，空的散列地址总能找到，并将记录存入。

    • 凋谢寻址法：Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中 H(key)为散列函数，m 为散列表长，di 为增量序列，可有下列三种取法：

      • 1)．di=1,2,3,…，m-1，称线性探测再散列；
      • 2)．di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)称二次探测再散列；
      • 3)．di= 伪随机数序列，称伪随机探测再散列。
    • 用凋谢定址法解决抵触的做法是：当抵触产生时，应用某种探测技术（线性探测法、二次探测法（解决线性探测的沉积问题）、随机探测法（和二次探测原理统一，不一样的是：二次探测以定值跳跃，而随机探测的散列地址跳跃长度是不定值））在散列表中造成一个探测序列。沿此序列一一单元地查找，直到找到给定的关键字，或者碰到一个凋谢的地址（即该地址单元为空）为止插入即可。

  • 2. 再哈希

    • 再哈希法又叫双哈希法，有多个不同的 Hash 函数，当发生冲突时，应用第二个，第三个，….，等哈希函数去计算地址，直到无抵触。尽管不易产生汇集，然而减少了计算工夫。

  • 3. 链地址法(Java HashMap 就是这么做的)

    • 链地址法的根本思维是：每个哈希表节点都有一个 next 指针，多个哈希表节点能够用 next 指针形成一个单向链表，将所有关键字为同义词的结点链接在同一个单链表中。

  • 4. 建设一个公共溢出区

    • 这种办法的根本思维是：将哈希表分为根本表和溢出表两局部，但凡和根本表发生冲突的元素，一律填入溢出表。

16. 问题思考的答疑

  • 1. 如何避免数据库中的用户信息被脱库？你会如何存储用户明码这么重要的数据吗？

    • 一. 应用 MD5 进行加密
    • 二. 字典攻打：如果用户信息被“脱库”，黑客尽管拿到的是加密之后的密文，但能够通过“猜”的形式来破解明码，这是因为，有些用户的明码太简略。
    • 三. 针对字典攻打，咱们能够引入一个盐（salt），跟用户明码组合在一起，减少明码的复杂度。
    • 四. 最好对明码验证次数进行限时间段限度。

  • 2. 在理论开发中，咱们应该如何用哈希算法解决问题？

    • 在理论开发中要衡量破解难度和计算工夫来决定到底应用哪种加密算法。

  • 3. 为何银行明码 6 个数字不易破解

    • 用户设置一个简略明码，进行加密后就变成 32 位，64 位，128 位等明码了，而后在网上传输就平安多了，个别这种加密明码和工夫戳也正相干。截获了也用途不大，就是把工夫参数传递过来了，服务器也和本地工夫比对的，超过 3 分钟他们就认为是非法音讯，它是一直变动的，破解很艰难。
    • 很多网站都有输出次数限度，所以对很多网站的明码破解都集中在加密算法上，很少进行字典式攻打了，当然黑客找到网站的破绽，绕过次数限度，也会进行字典式轰炸。

综合库：https://github.com/yangchong2…

视频播放器：https://github.com/yangchong2…

综合博客汇总：https://github.com/yangchong2…

正文完
android
发表至： android
2023-02-02
 0
关于android:刷爆-LeetCode-周赛-337位掩码回溯同余分桶动态规划打家劫舍贪心
关于android:纯干货Android知识点整理二
关于android:Android-高通Camx架构学习-第1章
关于android:快速入门Python基础知识

站内搜索

-「」