哈希函数
 
哈希函数是从关键字集合到地址集合的映射。这一映射过程称为哈希造表或散列，所得存储位置为哈希地址或散列地址。
 
哈希函数的构造方法
 
1.1直接定址法
 
取关键字或关键字的某个线性函数值为哈希地址。即：
 
H（key）=key或H(key)=a*key+b  （其中a和b为常数。）
 
由于直接定址所得地址集合和关键字集合的大小相同。因此，对于不同的关键字不会发生冲突。实际中使用这种哈希函数的情况很少。
 
1.2数字分析法
 
将设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
 
1.3平方取中法
 
取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数方法。（通常在选定哈希函数时不一定能知道关键字的全部情况，取其中那几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定）
 
1.4折叠法
 
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。关键字位数很多，而且关键字中每一位上的数字分布大致均匀时，可以采用折叠法得到哈希地址。在折叠法中数位叠加可以有移位叠加和间界叠加两种方法。
 
 
1.5除留余数法
 
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即：
 
H(key)=key MOD p,  p<=m
 
这是一种最简单，也是最常用的构造哈希函数的方法。他不仅可以对关键字直接取模（mod）,也可以在折叠，平方取中等运算后取模。使用除留余数法时，对p的选择很重要，若p选择不好容易产生同义词。
 
1.6随机数法
 
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数。通常，当关键字长度不等时采用此方法构造哈希函数较恰当。
 
总结：
 
实际工作中不同情况需要采用不同的哈希函数，通常，考虑的因素有：
 
（1）计算哈希函数所需时间（包括硬件指令因素）；
 
（2）关键字的长度。
 
（3）哈希表的大小。
 
（4）关键字的分布情况。
 
（5）记录的查找频率。
 
处理冲突的方法
 
将设哈希表的地址集为0~（n-1）,冲突是指由关键字得到的哈希地址为j(0<=j<=n-1)的位置上已存有记录，则处理冲突就是为该关键字的记录找到另一个空的哈希地址。在处理冲突的过程中可能得到一个地址序列Hi i=1,2,.....k,(Hi属于[0,n-1])即在处理哈希地址的冲突时，若得到的另外一个哈希地址H1仍然发生冲突，则求下一个地址H2。若H2仍冲突，则求H3.一次类推。直至Hk不发生冲突为止，则HK为记录在哈希表中的地址。常用的方法有：
 
开放定址法
Hi=(H(key)+di)MODm  i=1,2,...,k(k<=m-1) 其中：H(key)为哈希函数，m为哈希表表长；di为增量序列，可由下列三种取法：
 
A.di=1,2,3,...m-1称线性探测再散列
 
B.di=12,-12,22,-22,...,+_k2（k<=m/2）称二次探测在散列
 
C.di=伪随机数序列，称伪随机探测在散列。
 
（引入二次聚集，在处理同义词的冲突过程中又添加了非同义词的冲突，这种现象对查找不利）
 
 
用线性探测再散列处理冲突可以保证做到：只要哈希表未填满，总能找到一个不发生冲突的地址HK。而二次探测再散列只有在哈希表长m为形如4j+3(j为整数)的素数才有可能，随机探测在散列则取决于伪随机数列。
 
2.再哈希法
 
Hi=RHi(key)   i=1,2,...k   RHi均为不同的哈希函数，即在同义词产生地址冲突时，计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生聚集，但是增加了计算的时间。
 
3链地址法
 
将所有关键字为同义词的记录存储在同一线性链表中。将设某哈希函数产生的哈希地址在区间[0,m-1]上，则设立一个指针型变量。 Chain ChainHash[m];
 
其中每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在链表中插入的位置可以是表头和表未，也可以是中间，以保持同义词在同一线性链表中按关键字有序。
 
 
4..建立一个公共的溢出区
 
这也是处理冲突的一种方法。将设哈希函数值域为[0,m-1],则设向量HashTable[0...m-1]为基本表，每个分量存放一个记录，另设立向量OverTable[0...v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管他们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。（建立一个公共溢出区域，就是把冲突的都放在另一个地方，不在表里面。）
 
哈希表的查找及其分析
 
在哈希表上进行查找的过程和哈希造表的过程基本一致。给定K，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功。否则比较关键字，若和给定值相同，则查找成功。否则根据造表时设定的处理冲突的方法找下一地址，直至哈希表中某个位置为空或者表中所填记录的关键字等于给定值为止。
 
总结：
 
从哈希表的查找过程可见：
 
（1）虽然哈希表在关键字与记录的存储位置之间建立了直接映射，但由于冲突的产生，是的哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。仍需以平均查找长度作为衡量哈希表的查找效率的度量。
 
（2）查找过程中需和给定值进行比较的关键字的个数取决于三要素：哈希函数，处理冲突的方法，哈希表的填充因子。（哈希函数的好坏影响出现冲突的频繁程度）
 
对同样一组关键字，设定相同的哈希函数，则不同的处理冲突的方法得到的哈希表不同。如下例1例2两个哈希表，在记录中查找概率相同的前提下，前者的平均查找长度为：
 
ASL（12）=1/12（1*6+2*4+3+4）=1.75（前者链地址法）
 
ASL（12）=1/12（1*6+2+3*3+4+9）=2.5（后者线性探测再散列）
 
线性探测再散列在处理冲突的过程中容易产生记录的二次聚集，如哈希地址不相同的记录又产生新的冲突，而链地址法处理冲突不会发生类似情况，因为哈希地址不同的记录在不同的链表中。
 
在一般情况下，处理冲突方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。
 
哈希表的装填因子定义为： a=(表中填入的记录数)/(哈希表的长度)
 
a标志哈希表的装满程度，a越小，发生冲突的可能性越小，a越大，表中填入的记录越多，发生冲突的可能性越大，查找时给定值与之进行比较的关键字的个数也就越多。
 
案例
 
例1：
 
例2
 
 
查找成功和查找不成功的平均查找长度
 
查找成功
线性探测再散列的哈希表查找成功时的平均查找长度
Snl=1/2(1+1/(1-a))
 
随机探测再散列，二次探测再散列和再哈希的哈希表查找成功时的平均查找长度为：
Snr=-1/aln(1-a)
 
链地址法处理冲突的哈希表查找成功时的平均查找长度为：
 
Snc=1+a/2
 
由于哈希表在查找不成功时所用的比较次数也和给定值有关，则可类似定义哈希表在查找不成功时的平均查找长度为：查找不成功时需和给定值进行比较的关键字个数的期望值。
 
不同的处理冲突的方法构成的哈希表查找不成功的平均查找长度分别为：
 
Unl=1/2(1+1/(1-a)2)           ---->-线性探测再散列
 
Unr=1/(1-a)                  ------->伪随机探测再散列
 
Unc=a+e-a                               ---------------->链地址
 
分析：
 
长度为m的哈希表中装填有n个记录时查找不成功的平均查找长度。这个问题相当于要求在这张表中填入第n+1个记录时所需作的比较次数的期望值。
 
（假定：a.哈希函数是均匀的。即产生表中各个地址的概率相等。B.处理冲突后产生的地址也是随机的。）
 
由于哈希表中n个记录是先后填入的，查找每一个记录所需比较次数的期望值，恰为填入此记录时找到此哈希地址时所进行的比较次数的期望值。
 
总结：
 
哈希表的平均查找长度是a的函数，而不是n的函数。不管n多大，总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围内。（注意：若要在非链地址处理冲突的哈希表中删除一个记录，则需在该位置的记录上填入一个特殊符号，以免找不到他后面填入的同义词的记录）。
 

Hash冲突
 
什么是哈希冲突
 
 
 
理解哈希函数
 
 
关键字和它在表中存储位置之间存在一种函数关系。这个函数我们称为为哈希函数。
 hash:散列、杂凑 
 就是把任意长度的输入，通过散列算法，变成固定长度的输出，这种是一种压缩映射.
 
 
那么在这种情况下，不同的输入可能会产生相同的散列值，即这种状况下他们对应的哈希数的值是相同的，因为值相同所以不可能由散列值确定唯一的输入值，这种情况就是哈希冲突
 
键(key)经过hash函数得到的结果作为地址去存放当前的键值对(key-value)(hashmap的存值方式)，但是却发现该地址已经有值了，就会产生冲突。这个冲突就是hash冲突了。
 
换句话说就是：如果两个不同对象的hashCode相同，这种现象称为hash冲突。
 
解决哈希冲突
 
有以下的方式可以解决哈希冲突：
 
开放定址法
再哈希法
链地址法
建立公共溢出区
 
开放定址法
 
这种方法的意思是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
 
线性探测再散列
 当发生冲突的时候，顺序的查看下一个单元
二次(平方)探测再散列
 当发生冲突的时候，在表的左右进行跳跃式探测
伪随机探测再散列
 建立一个伪随机数发生器，并给一个随机数作为起点
 
再hash法
 
这种方式是同时构造多个哈希函数，当产生冲突时，计算另一个哈希函数的值。
 这种方法不易产生聚集，但增加了计算时间。
 
链地址法
 
将所有哈希地址相同的都链接在同一个链表中 ，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
 hashmap就是用此方法解决冲突的。
 
建立一个公共溢出区
 
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
 
优缺点
 
开放散列（open hashing）/ 拉链法（针对桶链结构）
 
优点：
 
在总数频繁变动的时候可以节省开销，避免了动态调整；
记录存储在节点里，动态分布，避免了指针的开销
删除时候比较方便
 
缺点：
 
因为存储是动态的，所以在查询的时候跳转需要更多的时间的开销
在key-value可以预知，以及没有后续增改操作时候，封闭散列性能优于开放散列
不容易序列化
 
封闭散列（closed hashing）/ 开放定址法
 
优点：
 
容易序列化
如果可以预知数据总数，可以创建完美哈希数列
 
缺点：
 
存储的记录数目不能超过桶组数，在交互时候会非常麻烦
使用探测序列，计算时间成本过高
删除的时候比较麻烦

如何理解冲突域和广播域？
 
转载
 
冲突域：
 
【定义】在同一个冲突域中的每一个节点都能收到所有被发送的帧。简单的说就是同一时间内只能有一台设备发送信息的范围。
 
【分层】基于OSI的第一层物理层
 
【设备】第二层设备能隔离冲突域，比如Switch。交换机能缩小冲突域的范围，交换接的每一个端口就是一个冲突域。
 
广播域：
 
【定义】网络中能接收任一设备发出的广播帧的所有设备的集合。简单的说如果站点发出一个广播信号，所有能接收收到这个信号的设备范围称为一个广播域。
 
【分层】基于OSI的第二层数据链路层
 
【设备】第三层设备才能隔离广播域，比如Router。路由器能隔离广播域，其每一个端口就是一个广播域。
 
​下面通过三个例子来说明：
 
例子一：一个Switch直连三台PC和一台hub，而hub下直连有2台PC。
 
 
​​图中已经给出了答案，可是，这个4个冲突域1个广播域是怎么算出来呢？
 
根据前面介绍的关于广播域的定义中我们知道 ，只有第三层设备才能隔离广播域。上图中并没有router等第三层设备，所以，这里的广播域没有被隔离。也就是说上图中的网络只有1个广播域。 
 
冲突域的计算，前面有说Switch能缩小冲突域，一个Switch端口其实就是一个冲突域，上图中有3台pc和1台hub直连到Switch上，所以，这里的冲突域为4个。 
 
第一个例子比较简单，下面我们在网络中有router第三层设备的例子
 
​一台router下直接连接三台hub，hub下都各自连有三台pc：
 
 
第三层设备router能隔离广播域，上图中router的三个端口分别直连了三个hub，因此得出有三个广播域。
 
但是，那3个冲突域是怎么来的呢？
 
其实，router他不但能隔离广播域，默认也是可以缩小冲突域的。所以上图中的router用3个端口将网络既分开成了3个广播域，又缩小成了3个冲突域。
 
第二个例子给了我们一个提醒，那就是路由器默认也是可以隔离冲突域的。
 
好了，下面我再看最后一个例子，这里都用上了常用的网络设备hub、Switch和router。 
 
一台router下连两台交换机和一台hub，两台交换机下分辨连有三台 PC，而hub下连有4台PC：
 
 
​上图所示网络，算出3个广播域不难，因为router有3个端口直连了2台交换机和1台集线器嘛。可是，冲突域不是7个吗？怎么是9个呢？两台交换机共使用了6个端口，外加路由器下还直连了一个集线器，这也是一个冲突域。于是，我可以得出6+1=7，7个冲突域啊。究竟是哪里算少了？对了，就是路由器到两台交换机之间也还是存在冲突域的。这一点也特别需要注意。
 
最后记录一下例子中提到的需要注意的地方了：
 
1、第二层设备只能隔离冲突域，第三层设备才能隔离广播域；
 
2、路由器不但能隔离广播域，默认也是可以隔离冲突域的；
 
3、路由器下直连交换，则路由器到交换机之间也是存在冲突域的。
 
 
 
 
 
总结：
 
​1、第二层设备只能隔离冲突域，第三层设备才能隔离广播域
 
​2、路由器不但能隔离广播域，默认也是可以隔离冲突域的
 
​3、路由器下直连交换，则路由器到交换机之间也是存在冲突域的
 
​4、router不仅能能够分割广播域，也能缩小冲突域
 
​5、交换机的每一个端口是一个冲突域
 
​6、集线器下连的所有端口是一个冲突域（上一个设备是路由器）

   首先，Android依赖包冲突其实并不是简单的不同模块依赖了相同库的不同版本，因为系统会自动选择高版本，同时给这两个模块使用。冲突只存在两种情况
 
    引用了本地jar文件
 由于引用的jar是会直接编译到项目里的，如果项目的两个module同时引入了相同的本地jar文件, 就会存在相同的类有多个实现，及duplicated defined class。这种情况比较好分析和定位，去掉其中一个即可。
   不同模块引用了相同的远程库(比如maven库)的不同版本，且这两个版本不兼容
 这类冲突主要是Android Support类, 目前Android已经退出AndroidX包了。
 这种情况就比较难分析，本文将就我曾经遇到过的一个案例来分析此类包冲突的解决方案流程。
 
 
问题分析
 
 当时编译一个项目时遇到这个错误
 
 
 
  Learn how to resolve the issue at https://developer.android.com/studio/build/dependencies#duplicate_classes.
 
 
  Program type already present: android.support.design.widget.CoordinatorLayout$Behavior
 
 
 CoordinatorLayout$Behavior类存在多次定义。这个主要是因为这个类在support的低版本26.xx上，是在design库里的。而到了support的27.xx，这个类却到了support-core-ui库。
 
com.android.support:design:26.1.0
 
 
com.android.support:support-core-ui:27.1.0
 
 
    
 
     所以如果你有些模块引用了design:26.xx, 其他模块引用了support-core-ui:27.xx, 然后就会出现CoordinatorLayout在两个库都存在的问题
 
    如果design也是27版本，该库不会有CoordinatorLayout这个类，也就不会报错了。
 
    解决方法，就是让这两个库保持一样的版本。通过修改app/build.gradle, 让这两个库都使用较高的新版本，然后就可以保持一致了(全局使用高版本库替换)
 
 
 
问题原因
 
 
 
    上面分析出了原因，但是为甚会出现这种情况呢？我们具体来分析下：
 
通过./gradlew dependencies即可查看包的依赖分析，该命令非常有效，大家可以试试
 
ModuleA通过引用support 27版本引入了support-core-ui:27.1.1库
 
 
ModuleB直接依赖design 26版本，尽管因为ModuleA引入了support 27导致ModuleB依赖的support-core-ui升级到了27，
 
但是design库并没有升级，从而导致同时存在design:26和support-core-ui:27, 进而引入了两个相同类CoordinatorLayout
 
 
 
 
/**************************************************
 * 本文来自CSDN博主"一点码客"，喜欢请顶部点击关注
 * 转载请标明出处:http://blog.csdn.net/itchosen
 ***************************************************/
 
如需实时查看更多更新文章，请关注公众号"一点码客"，一起探索技术