哈希税号是什么

我们先来讲个故事哈。

有一个人每次打开区块链文章，都意气风发，暗暗下决心要发愤图强，看了一会儿，发现很难看懂什么，硬逼着自己学习，却已是强弩之末，最后只能末学肤受，学了个皮毛而已。

那个人就是我哈，希望大家不要末学肤受，而能食髓知味，深刻理解区块链知识。

这四个成语。

意气风发～发奋图强～强弩之末～末学肤受

每个成语的第一个字，是前一个成语的最后一个字，组成了一个成语链的链式结构。

我们来类比一下，区块链的链式结构。

区块链0，1，2，3的链式结构是靠什么形成的呢？

是靠前一个区块的哈希值，也叫做父区块哈希值。

区块0是区块1的父区块。

区块1是区块0的子区块。

区块0的哈希值对区块1而言，就是父区块的哈希值。

父区块哈希值，就是上面成语链式结构里，把前后两个成语连接起来的那个字。

要理解区块链链式结构，还要理解什么叫哈希。

再讲个故事哈。

小黑同学要把一袋猫粮快递给大白老师。

他让哈希公司的快递员上门取件，打包完成后，拿到了快递单号。

这个寄快递的过程中，有三个关键步骤。

1.选择要寄送的物品。

2.选择哈希快递公司，对物品进行快递打包。

3.拿到快递单号。

哈希公司给的快递单号就是哈希值。

大白老师对小黑选择的哈希公司很满意。

1.不论小黑寄的东西有多大，经过哈希公司打包后，拿到手的快递包裹都一样大。

2.哈希公司打印出来的快递单号也就是哈希值，除了让你查询物流的实时状况，还可以让你知道包裹中的物品有没有被人调包或撰改。

比如小黑寄给大白的猫粮，在运送过程中，哪怕袋子上的配料表，被人改了一个标点符号，哈希公司给的快递单号，也就是哈希值都会实时发生变化，警示小黑快递包裹发生了异常情况。

哈希公司确实很厉害哈。

在两个关系上进行连接用多线程来加速主要有两种方法哈希连接和排序合并连接。

多数OLTP DBMS都没有实现哈希连接

但是少量目标元组的索引嵌套连接和哈希连接是差不多的

连接算法的设计目标：

提高cache

影响DBMS cache未命中的因素：

对于OLAP DBMS哈希连接是最重要的操作

充分利用多核来加速哈希连接算法是至关重要的——让所有的核都跑起来，又不想要内存受限

哈希连接R⨝S氛围三个阶段：划分（可以没有）用哈希函数在连接关键字上将R和S的元组进行分区（为下一步索引的构建以及最后的探查做准备）；构建，扫描关系R在连接关键字上创建一个哈希表；探查，对于S中的每个元组，查找它的连接关键字是不是在R的哈希表中，如果找到，那么输出合并好的元组。

两种方法

只扫描输入的关系一次，并动态产生输出

所有线程更新在一个全局的分区集合；必须用latch来同步线程；最终的结果是可用的哈希表，传输一次数据

每个线程有自己的分区；在所有线程都完成后需要整合，传输两次数据

也叫基数分区，和基数排序的原理很像，都是一位一位数字的来排。

多次扫描输入的关系；只在最后物化结果；也叫基数哈希连接

多步

对第二列数字也是递归重复，直到分区的目标数字建立

线程会扫描R(或分区)中的元组

对于每个元组，哈希它的连接属性并把它加入到哈希表中相应的bucket中（bucket只有几个cache line大小）

有两个需要考虑的问题：

一些的哈希函数介绍...

1.链式哈希

维持一个bucket的链表

通过把有一样哈希值的元素放到同一个bucket中

在查找时，看一个元素有没有，需要扫描其哈希值对应的bucket；插入和删除也是

为了减少连接时的比价，减少哈希值的冲突是至关重要的。

链式哈希大概需要R中元素的一般的slots。

key一定在邻居范围内或不存在。

对于S中每个元组，都会哈希它的连接key检查它在由R构建的哈希表中相应的bucket里有没有对应的元组。

如果输入分区了，那么也要给每个线程进行一个独立的分区。否则需要同步他们在访问S时的游标。

在构建阶段当关键字可能在哈希表中可能不存在时创建一个布隆过滤器

在探查哈希表前线程会先检查过滤器；也叫sideways information passing

基于分区的连接在多数情况都要比不分区的算法性能好。

哈希表是一种数据结构～

哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录， 那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。 (关键字就是所要存储的数据，存储位置相当于数组的索引)

当然，可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1，而是由关键字(数据本身)通过哈希函数得到

eg1. 将26个小写字母存储到数组  int [26] a。

a对应a[0]，b对应a[1]，c对应a[3]……以此类推。

那么，数组 int [26] a 就是一个哈希表！

例1中，关键字(小写字母)是如何得到自己对应的索引(存储位置)的呢？

关键字的ASCII值减去a的ASCII值！

上面说过，关键字通过哈希函数得到索引，所以，f(ch)就是本例题的哈希函数。

这样，我们就在关键字和数字(存储位置)之间建立了一个确定的对应关系f。

关键字与数字是一一对应的，由于数组本身支持随机访问，所以，当查找关键字时，只需要O(1)的查找操作，也就是实现了不经过任何比较，一次便能得到所查记录。

哈希表中 哈希函数的设计 是相当重要的，这也是建哈希表过程中的关键问题之一。

假如，我们所要存储的数据其关键字是一个人的身份证号(18位数字)，这个时候我们该怎么计算关键字对应的索引呢？

比如一个人的身份证号是 411697199702076425，我们很难像例1那样直接让关键字与数字建立一一对应的关系，并且保证数字适合作为数组的索引。

在这种情况下，通过哈希函数计算出的索引，即使关键字不同，索引也会有可能相同。这就是 哈希冲突

当索引相同时，我们该怎么存储数据呢？如何解决哈希冲突，是我们建哈希表的另一个关键问题。

哈希表充分体现了空间换时间这种经典的算法思想。

关键字是大整数时，比如上面我们举的身份证号例子，411697199702076425

假如我们能开辟一个 999999999999999999 大的空间，这样就能直接把身份证号作为关键字存储到数组中，这样可以用O(1)时间完成各项操作

假如我们只有 1 的空间，我们需要把所有信息存储到这个空间中(也就是所有数据都会产生哈希冲突)，我们只能用O(n)时间完成各项操作

事实上，我们不可能开辟一个如此大的空间，也不可会开辟如此小的空间

无限空间时，时间为O(1)

1的空间时，时间为O(n)

而哈希表就是在二者之间产生一个平衡，即 空间和时间的平衡 。

1.哈希函数的设计

2.解决哈希冲突

3.哈希表实现时间和空间的平衡

后续会详细说明这三个关键问题～

从源码来窥其一斑！

我们都知道hashMap不是线程安全的，因为在扩容方法中很容易出现死循环，hashTable使用锁的方式比较简单暴力，几乎在所有操作方法上都加了synchronized锁，导致总体性能很差，concurrentHashmap凭借线程安全且性能优异一直都是高并发中的首选key-value型数据结构；

concurrentHashmap的高性能有以下原因：

一，分段锁：jdk8中对concurrentHashmap进行了改进，抛弃了jdk7中新建segment作为分段锁的过程，jdk8中虽沿用了这种分段锁的思想，却直接使用数组中的数据作为 分段锁保证concurrentHashmap在上锁的时候只针对数组下标下的数据进行上锁 （比如如果数组长度为256，那么每次put平均只有1/256的数据被锁），而大多数其他的数据还是能进行正常的增删改操作，无需阻塞等待，这无疑极大的 降低了锁的粒度，提升了性能。

二，红黑树 ：jdk8中引入了红黑树结构，在单个数组下标内的数据达到8以后，会自动转换为红黑树进行存储， 使用大O表示法表示效率的话，红黑树的查找效率为O(log(n))，而链表的效率为O（n） ，当数据量越来越大的时候，红黑树的效率明显好于链表，所以concurrentHashmap性能得到很大提升；

现在我们主要从put方法中的主要方法来分析性能的提升：

spread(key.hashCode())//作用是再次哈希，减少冲突 ，源码如下

其中涉及到的位运算有

>>>16：无符号右移16位，空位以0补齐 。

^:异或运算符-->相同为0，不同为1； &：与运算符-->全1得1，否则0；

(h ^ (h >>>16)) &HASH_BITS所以这句代码的意思就是不仅消除高16位的影响，同时获得正整数的hash值

再来看后面的方法， 如上图：

1，就是判断当这个hash表还是空的时候，调用initTable进行初始化； 2，使用(n - 1) &hash)计算数组下标，如果数据指定下标处为null，则直接插入，注： cas是java8中的concurrentHashmap引入的线程安全判断，CAS算法做为乐观锁 ；

3，(fh = f.hash) == MOVED，走到此处说明下标内有node，且该node的值为-1（MODED=-1),搜索全类发现MODED是在调用有参构造器ForwardingNode中默认写入的，而这个调用处刚好在transfer方法中，所以我们推断，扩容的时候先将数组下标内的node.hash置为-1！ 同时在3这一步中调用helpTransfer(tab, f)参与扩容，并把数据写入；

4，走到这说明node不是空的，也没在扩容，那么锁住该下标下的node，并把新value插入链表中； 5，如果锁住的这个node能实例化为TreeBin，则代表已经转化为红黑树进行存储，将数据插入红黑树中； 6，判断在4,5中计算得到的数组下标内所有节点总数， 如果满足转化为红黑树的条件（节点数大于8），则自动转化为红黑树进行存储！

总的来说，concurrentHashmap之所以性能高就是因为使用了分段锁和红黑树！

至于conrrentHashmap其他的方法的源码分析，后期会补上的，更多的技术分享，敬请关注！

(1)存储键值对，实现快速存取数据；

(2)允许键/值为null，但不允许重复的键；

(3)非同步synchronized(比同步快)，线程不安全；

注：让HashMap同步： Map m = Collections.synchronizeMap(hashMap)

(4)实现Map接口，对键值对进行映射，不保证有序(比如插入的顺序)

注：Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。

(5)HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”

(6)HashMap添加元素时，是使用自定义的哈希算法

(1)不存储键值对，仅存储对象；

(2)不允许键/值为null；

(3)线程安全(速度慢)，采用synchronize关键字加锁原理(几乎在每个方法上都加锁)，；

(4)实现了Set接口，不允许集合中有重复的值。注：将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，

比较对象的值是否相等，以确保set中没有储存相等的对象。hashCode()可能相同，用equals()判断对象的相等性。

(5)Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”；

(6)Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

(1)Java并发包java.util.concurrent中的一个线程安全且高效的HashMap实现

(2)不允许键/值为null；

(3)线程安全：在JDK1.7中采用“分段锁”的方式，1.8中直接采用了CAS（无锁算法）+ synchronized。

Entry：HashMap是一个用于存储Key-Value键值对的集合，每一个键值对叫做Entry，这些Entry分散存储在一个数组当中。

hashMap是在bucket中储存键对象和值对象，作为Map.Entry

bucket：HashMap初始化时，创建一个长度为capacity的Entry数组，这个数组里可以存储元素的位置被称为“桶(bucket)”，

每个bucket都有其指定索引，系统可以根据其索引快速访问该bucket里存储的元素。

loadFactor：负载因子。默认值DEFAULT_LOAD_FACTOR = 0.75f；

capacity：容量，指的是数组的长度

threshold：阈值=capacity*loadFactor。超过阈值则扩容为原来的两倍。

size：HashMap的大小，它是HashMap保存的键值对的数量。

HashMap是基于hashing的原理，底层使用哈希表结构(数组+链表)实现。使用put(key,value)存储对象，使用get(key)获取对象。

理解为，数组中存储的是一个Entry，并且作为链表头结点，头结点之后的每个节点中储存键值对对象Entry。

给put()方法传递键和值时，先对键调用hashCode()方法计算hash从而得到bucket位置，进一步存储，

HashMap会根据当前bucket的占用情况自动调整容量(超过负载因子Load Facotr则resize为原来的2倍)。

扩容扩的是数组的容量，发生碰撞后当链表长度到达8后，链表上升为红黑树，提高速度。

根据键key的hashcode找到bucket位置，然后遍历链表节点，调用equals(用来获取值对象)方法确定键值对，找到要找的值对象。

a.对key的hashCode做hash操作(高16bit不变，低16bit和高16bit做了一个异或)

b.计算下标(n-1) &hash，从而获得buckets的位置 //h &(length-1)

数字分析法、平方取中法、分段叠加法、 除留余数法、 伪随机数法。

其他解决hash冲突办法：开放定址法、链地址法、再哈希法。

根据hashcode来划分的数组，如果数组的坐标相同，则进入链表这个数据结构中，jdk1.7及以前为头插法，jdk1.8之后是尾插法，

在jdk1.8之后，当链表长度到达8的时候，jdk1.8上升为红黑树。存的时候按照上面的方式存，取的时候根据equals确定值对象。

1.常见问题：集合类、数据结构、线程安全、解决碰撞方法、hashing概念和方法、equals()和hashCode()的应用、不可变对象的好处

https://blog.csdn.net/weixin_42636552/article/details/82016183

https://blog.csdn.net/u012512634/article/details/72735183

https://blog.csdn.net/zaimeiyeshicengjing/article/details/81589953

https://blog.csdn.net/aura521521/article/details/78462459

在并发使用到HashMap的时候，往往不建议直接用HashMap，因为HashMap在并发写数据的时候容易因为rehash的过程产生环形链表的情况。所以在并发使用Map结构时，一般建议使用ConcurrentHashMap。

在JDK1.7中ConcurrentHashMap采用了 数组+Segment+分段锁 的方式实现。

从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，内部大量采用CAS操作。并发控制使⽤ synchronized 和 CAS 来操作。 （JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但

是已经简化了属性，只是为了兼容旧版本；

JDK1.8的Nod节点中value和next都用volatile修饰，保证并发的可见性。

可以理解为，synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效率⼜提升 N 倍。

Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的；

Hashtable(同⼀把锁) :使⽤ synchronized 来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤get，竞争会越来越激烈效率越低；

总结一下：

JavaGuide

哈希算法就是一种特殊的函数，不论输入多长的一串字符，只要通过这个函数都可以得到一个固定长度的输出值，这就好像身份证号码一样，永远都是十八位而且全国唯一。

哈希算法的输出值就叫做哈希值。哈希算法也被称为“散列”，是区块链的四大核心技术之一。是能计算出一个数字消息所对应的、长度固定的字符串。

哈希算法原理：

Hash算法的原理是把输入空间的值映射到Hash空间内，由于Hash值的空间远小于输入的空间，而且借助抽屉原理 ，可以得出一定会存在不同的输入被映射成相同输出的情况，如果一个Hash算法足够好，那么他就一定会有更小的发生冲突的概率，也就是说，一个好的Hash算法应该具有优秀的 抗碰撞能力。

Update: 很多设计都是类似的, 比如 Hashmap , ThreadLocalMap , LongAdder 的 Cell 都是设计为 2^n , 归根到底都是因为要hash寻址CAS也是，不少地方用到来不挂起线程等待锁，不过很耗时，所以 LongAdder 中用空间换时间创建一个数组，这个跟dp的思路相同；而创建数组的过程中对多线程只创建一次，用DCL校验的做法，和多线程的单例模式一样。不得不说还是要理解思想，有了这些想法，各种数据结构就都懂为什么这样写了，并且还可以自己设计。

原文: threadlocalmap, hashmap哈希和寻址异同随想

异: hash算法

也就是一个是高低位异或，另一个是每次增加1640531527。为什么是1640531527? 看看这个数和int最大值的关系，并且注意一下结尾的数字7联想hash规则，就知道了。

get 碰撞:

一个顺着linkedlist找，另一个往后index找, 这是两种map内存的结构不同决定的: hashmap存的 Node 和threadlocalmap存的 Entry (有无 next ):

同: hash寻址:

至于为什么threadLocal要用自定义的threadlocalmap附着在每个thread上面，因为:

暂时突然想到这么多。感想: threadlocalmap比hashmap还是要简单的

采用了分段锁的思想，将哈希桶数组分成一个个的Segment数组（继承ReentrantLock），每一个Segment里面又有多个HashEntry，也是被volatile修饰的，是为了保证在数组扩容时候的可见性，HashEntry中又有key，hash，value，next属性，而value，next又是被volatile修饰为了保证多线程环境下数据修改时的可见性，多线程环境下ConcurrentHashMap会对这些小的数组进行加锁，这样多线程操作Map就相当于是操作单线程环境下的HashMap，比如A线程对其中一个段进行写操作的时候线程B就不能对其进行写操作，但是线程B可以对其他的段进行写操作，从而实现并发修改和访问。

JDK1.8的ConcurrentHashMap摒弃了分段锁的思想，采用jdk1.8中HashMap的底层机构，Node数组+链表+红黑树。Node是继承了Entry的一个内部类，他的value和next都是被volatile修饰的原因也是为了保证多线程下修改数据的可见性。

采用CAS+synchronized实现更加细粒度的锁，将锁的级别控制在更细粒度的哈希桶数组元素的级别，只需要锁住链表头节点（红黑树的根节点）就不会影响到其他哈希桶数组元素的读写，大大的提高了并发度。

是不需要加锁的，因为Node节点使用了volatile修饰了value和next节点，而在jdk8中同样也是使用了volatile修饰了value和next节点，这样保证可见性了就不需要加锁了。

key不能为空，无法解释，没有什么可说的，可能就是作者的想法。

value不能为空是因为ConcurrentHashMap是工作在多线程环境下的，如果调用get方法，返回null，这个时候就存在二义性，因为ConcurrentHashMap不知道是没有这个key，还是这个key对应的值是不是null。所以干脆不支持value为null。

HashMap的迭代器是强一致性的，而ConcurrentHashMap的迭代器是弱一致性的，因为在多线程环境下，在创建迭代器的过程中，内部的元素会发生变化，如果是在已经遍历过去的数据中发生变化，迭代器是无法反映出来数据发生了改变，如果是发生在未迭代的数据时，这个时候就会反映出来，强一致性就是说只要迭代器创建出来之后数据就不会发生改变了。这样设计的好处就是迭代器线程可以使用原来的老数据进行遍历，写线程可以并发的完成改变，这样就保证了多个线程执行的时候的连续性和可拓展性，提升了并发性能。

JDK1.7中，并发度就是ConcurrentHashMap中的分段个数，即Segment[]数组的长度，默认是16，这个值可以在构造函数中设置。如果自己设置了并发度那么就会和HasHMap一样会去找到大于等于当前输入值的最小的2的幂指数作为实际并发度。如果过小就会产生锁竞争，如果过大，那么就会导致本来位于同一个Segment的的访问会扩散到不同的Segment中，导致性能下降。

JDK1.8中摈弃了Segment的概念，选择使用HashMap的结构，并发度依赖于数组的大小。

ConcurrentHashMap效率高，因为hashTable是给整个hash表加锁，而ConcurrentHashMap锁粒度要更低。

使用Collections.synchronizedMap（Map类型的对象）方法进行同步加锁，把对象转换为SynchronizedMap<K,V>类型。其实就是对HashMap做了一次封装，多个线程竞争一个mutex对象锁，在竞争激烈的情况下性能也非常差，不推荐使用。