精华内容
下载资源
问答
  • Oracle里的哈希连接原理

    千次阅读 2014-05-15 21:28:47
    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。 在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法...

    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

    在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷。对于排序合并连接,如果两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。

    为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,Oracle在Oracle 7.3中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。

    在Oracle 10g及其以后的Oracle数据库版本中,优化器(实际上是CBO,因为哈希连接仅适用于CBO)在解析目标SQL时是否考虑哈希连接是受限于隐含参数_HASH_JOIN_ENABLED,而在Oracle 10g以前的Oracle数据库版本中,CBO在解析目标SQL时是否考虑哈希连接是受限于参数HASH_JOIN_ENABLED。

    _HASH_JOIN_ENABLED的默认值是TRUE,表示允许CBO在解析目标SQL时考虑哈希连接。当然,即使你将该参数的值改成了FALSE,我们使用USE_HASH Hint依然可以让CBO在解析目标SQL时考虑哈希连接,这说明USE_HASH Hint的优先级高于参数_HASH_JOIN_ENABLED。

       

    如果两个表(这里将它们分别命名为表T1和表T2)在做表连接时使用的是哈希连接,则Oracle在做哈希连接时会依次顺序执行如下步骤:

    1、  首先Oracle会根据参数HASH_AREA_SIZE、DB_BLOCK_SIZE和_HASH_MULTIBLOCK_IO_COUNT的值来决定Hash Partition的数量(Hash Partition是一个逻辑上的概念,所有Hash Partition的集合就被称之为Hash Table,即一个Hash Table是由多个Hash Partition所组成,而一个Hash Partition又是由多个Hash Bucket所组成);

    2、  表T1和T2在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集会被Oracle选为哈希连接的驱动结果集,这里我们假设T1所对应的结果集的数据量相对较小,我们记为S;T2所对应的结果集的数据量相对较大,我们记为B;显然这里S是驱动结果集,B是被驱动结果集;

    3、  接着Oracle会遍历S,读取S中的每一条记录,并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算,这个哈希运算会使用两个内置哈希函数,这两个哈希函数会同时对该连接列计算哈希值,我们把这两个内置哈希函数分别记为hash_func_1和hash_func_2,它们所计算出来的哈希值分别记为hash_value_1和hash_value_2;

    4、  然后Oracle会按照hash_value_1的值把相应的S中的对应记录存储在不同Hash Partition的不同Hash Bucket里,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值。注意,存储在Hash Bucket里的记录并不是目标表的完整行记录,而是只需要存储位于目标SQL中的跟目标表相关的查询列和连接列就足够了;我们把S所对应的每一个Hash Partition记为Si;

    5、  在构建Si的同时,Oracle会构建一个位图(BITMAP),这个位图用来标记Si所包含的每一个Hash Bucket是否有记录(即记录数是否大于0)

    6、  如果S的数据量很大,那么在构建S所对应的Hash Table时,就可能会出现PGA的工作区(WORK AREA)被填满的情况,这时候Oracle会把工作区中现有的Hash Partition中包含记录数最多的Hash Partition写到磁盘上(TEMP表空间);接着Oracle会继续构建S所对应的Hash Table,在继续构建的过程中,如果工作区又满了,则Oracle会继续重复上述挑选包含记录数最多的Hash Partition并写回到磁盘上的动作;如果要构建的记录所对应的Hash Partition已经事先被Oracle写回到了磁盘上,则此时Oracle就会去磁盘上更新该Hash Partition,即会把该条记录和hash_value_2直接加到这个已经位于磁盘上的Hash Partition的相应Hash Bucket中;注意,极端情况下可能会出现只有某个Hash Partition的部分记录还在内存中,该Hash Partition的剩余部分和余下的所有Hash Partition都已经被写回到磁盘上

    7、  上述构建S所对应的Hash Table的过程会一直持续下去,直到遍历完S中的所有记录为止;

    8、  接着,Oracle会对所有的Si按照它们所包含的记录数来排序,然后Oracle会把这些已经排好序的Hash Partition按顺序依次、并且尽可能的全部放到内存中(PGA的工作区),当然,如果实在放不下的话,放不下的那部分Hash Partition还是会位于磁盘上。我认为这个按照Si的记录数来排序的动作不是必须要做的,因为这个排序动作的根本目的就是为了尽可能多的把那些记录数较小的Hash Partition保留在内存中,而将那些已经被写回到磁盘上、记录数较大且现有内存已经放不下的Hash Partition保留在磁盘上,显然,如果所有的Si本来就都在内存中,也没发生过将Si写回到磁盘的操作,那这里根本就不需要排序了

    9、     至此Oracle已经处理完S,现在可以来开始处理B了;

    10、 Oracle会遍历B,读取B中的每一条记录,并对B中的每一条记录按照该记录在表T2中的连接列做哈希运算,这个哈希运算和步骤3中的哈希运算是一模一样的,即这个哈希运算还是会用步骤3中的hash_func_1和hash_func_2,并且也会计算出两个哈希值hash_value_1和hash_value_2;接着Oracle会按照该记录所对应的哈希值hash_value_1去Si里找匹配的Hash Bucket;如果能找到匹配的Hash Bucket,则Oracle还会遍历该Hash Bucket中的每一条记录,并会校验存储于该Hash Bucket中的每一条记录的连接列,看是否是真的匹配(即这里要校验S和B中的匹配记录所对应的连接列是否真的相等,因为对于Hash运算而言,不同的值经过哈希运算后的结果可能是一样的),如果是真的匹配,则上述hash_value_1所对应B中的记录的位于目标SQL中的查询列和该Hash Bucket中的匹配记录便会组合起来,一起作为满足目标SQL连接条件的记录返回;如果找不到匹配的Hash Bucket,则Oracle就会去访问步骤5中构建的位图,如果位图显示该Hash Bucket在Si中对应的记录数大于0,则说明该Hash Bucket虽然不在内存中,但它已经被写回到了磁盘上,则此时Oracle就会按照上述hash_value_1的值把相应B中的对应记录也以Hash Partition的方式写回到磁盘上,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值;如果位图显示该Hash Bucket在Si中对应的记录数等于0,则Oracle就不用把上述hash_value_1所对应B中的记录写回到磁盘上了,因为这条记录必然不满足目标SQL的连接条件;这个根据位图来决定是否将上述hash_value_1所对应B中的记录写回到磁盘的动作就是所谓的“位图过滤”我们把B所对应的每一个Hash Partition记为Bj

    11、 上述去Si中查找匹配Hash Bucket和构建Bj的过程会一直持续下去,直到遍历完B中的所有记录为止;

    12、 至此Oracle已经处理完所有位于内存中的Si和对应的Bj,现在只剩下位于磁盘上的Si和Bj还未处理;

    13、 因为在构建Si和Bj时用的是同样的哈希函数hash_func_1和hash_func_2,所以Oracle在处理位于磁盘上的Si和Bj的时候可以放心的配对处理,即只有对应Hash Partition Number值相同的Si和Bj才可能会产生满足连接条件的记录;这里我们用Sn和Bn来表示位于磁盘上且对应Hash Partition Number值相同的Si和Bj

    14、 对于每一对儿Sn和Bn,它们之中记录数较少的会被当作驱动结果集,然后Oracle会用这个驱动结果集的Hash Bucket里记录的hash_value_2来构建新的Hash Table,另外一个记录数较大的会被当作被驱动结果集,然后Oracle会用这个被驱动结果集的Hash Bucket里记录的hash_value_2去上述构建的新Hash Table中找匹配记录;注意,对每一对儿Sn和Bn而言,Oracle始终会选择它们中记录数较少的来作为驱动结果集,所以每一对儿Sn和Bn的驱动结果集都可能会发生变化,这就是所谓的“动态角色互换”

    15、 步骤14中如果存在匹配记录,则该匹配记录也会作为满足目标SQL连接条件的记录返回;

    16、 上述处理Sn和Bn的过程会一直持续下去,直到遍历完所有的Sn和Bn为止。

     

    对于哈希连接的优缺点及适用场景,我们有如下总结:

    Ÿ     哈希连接不一定会排序,或者说大多数情况下都不需要排序;

    Ÿ     哈希连接的驱动表所对应的连接列的可选择性应尽可能的好,因为这个可选择性会影响对应Hash Bucket中的记录数,而Hash Bucket中的记录数又会直接影响从该Hash Bucket中查找匹配记录的效率;如果一个Hash Bucket里所包含的记录数过多,则可能会严重降低所对应哈希连接的执行效率,此时典型的表现就是该哈希连接执行了很长时间都没有结束,数据库所在database server上的CPU占用率很高,但目标SQL所消耗的逻辑读却很低,因为此时大部分时间都耗费在了遍历上述Hash Bucket里的所有记录上,而遍历Hash Bucket里记录这个动作是发生在PGA的工作区里,所以不耗费逻辑读

    Ÿ     哈希连接只适用于CBO、它也只能用于等值连接条件(即使是哈希反连接,Oracle实际上也是将其转换成了等价的等值连接)

    Ÿ     哈希连接很适合于一个小表和大表之间的表连接,特别是在小表的连接列的可选择性非常好的情况下,这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当

    Ÿ     当两个表做哈希连接时,如果这两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集所对应的Hash Table能够完全被容纳在内存中时(PGA的工作区),则此时的哈希连接的执行效率会非常高。

     

    我们可以借助于10104事件所产生的trace文件来观察目标SQL在做哈希连接时的大致过程和一些统计信息(比如用了多少个Hash Partition、多个少Hash Bucket以及各个Hash Bucket都分别有多少条记录等),10104事件在我们实际诊断哈希连接的性能问题时非常有用。

     

    使用10104事件观察目标SQL做哈希连接的具体过程为:

    oradebug setmypid

    oradebug event 10104 trace name context forever, level 1

    set autotrace traceonly

    实际执行目标SQL(必须要实际执行该SQL,不能用explain plan for)

    oradebug tracefile_name

     

    一个典型的10104事件所产生的trace文件内容为如下所示:

    kxhfInit(): enter

    kxhfInit(): exit

    *** RowSrcId: 1 HASH JOIN STATISTICS (INITIALIZATION) ***

    Join Type: INNER join

    Original hash-area size: 3642760

    Memory for slot table: 2826240

    Calculated overhead for partitions and row/slot managers: 816520

    Hash-join fanout: 8

    Number of partitions: 8

    Number of slots: 23

    Multiblock IO: 15

    Block size(KB): 8

    Cluster (slot) size(KB): 120

    Minimum number of bytes per block: 8160

    Bit vector memory allocation(KB): 128

    Per partition bit vector length(KB): 16

    ……省略显示部分内容

      Slot table resized: old=23 wanted=12 got=12 unload=0

    *** RowSrcId: 1 HASH JOIN RESIZE BUILD (PHASE 1) ***

    Total number of partitions: 8

    Number of partitions which could fit in memory: 8

    Number of partitions left in memory: 8

    Total number of slots in in-memory partitions: 8

    kxhfResize(enter): resize to 14 slots (numAlloc=8, max=12)

    kxhfResize(exit): resized to 14 slots (numAlloc=8, max=14)

      set work area size to: 2215K (14 slots)

    *** RowSrcId: 1 HASH JOIN BUILD HASH TABLE (PHASE 1) ***

    Total number of partitions: 8

    Number of partitions left in memory: 8

    Total number of rows in in-memory partitions: 1000

       (used as preliminary number of buckets in hash table)

    Estimated max # of build rows that can fit in avail memory: 79800

    ### Partition Distribution ###

    Partition:0    rows:120        clusters:1      slots:1      kept=1

    Partition:1    rows:122        clusters:1      slots:1      kept=1

    ……省略显示部分内容

    Partition:6    rows:118        clusters:1      slots:1      kept=1

    Partition:7    rows:137        clusters:1      slots:1      kept=1

    *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

    Revised number of hash buckets (after flushing): 1000

    Allocating new hash table.

    *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

    Requested size of hash table: 256

    Actual size of hash table: 256

    Number of buckets: 2048

    Match bit vector allocated: FALSE

    *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

    Total number of rows (may have changed): 1000

    Number of in-memory partitions (may have changed): 8

    Final number of hash buckets: 2048

    Size (in bytes) of hash table: 8192

    qerhjBuildHashTable(): done hash-table on partition=7, index=0 last_slot#=3 rows=137 total_rows=137

    qerhjBuildHashTable(): done hash-table on partition=6, index=1 last_slot#=4 rows=118 total_rows=255

    ……省略显示部分内容

    qerhjBuildHashTable(): done hash-table on partition=1, index=6 last_slot#=2 rows=122 total_rows=880

    qerhjBuildHashTable(): done hash-table on partition=0, index=7 last_slot#=5 rows=120 total_rows=1000

    kxhfIterate(end_iterate): numAlloc=8, maxSlots=14

    *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) ***

    ### Hash table ###

    # NOTE: The calculated number of rows in non-empty buckets may be smaller

    #       than the true number.

    Number of buckets with   0 rows:       1249

    Number of buckets with   1 rows:        626

    Number of buckets with   2 rows:        149

    Number of buckets with   3 rows:         21

    Number of buckets with   4 rows:          3

    Number of buckets with   5 rows:          0

    ……省略显示部分内容

    Number of buckets with between  90 and  99 rows:          0

    Number of buckets with 100 or more rows:          0

    ### Hash table overall statistics ###

    Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799

    Total number of rows: 1000

    Maximum number of rows in a bucket: 4

    Average number of rows in non-empty buckets: 1.251564

    Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000

    qerhjFetch: max probe row length (mpl=0)

    *** RowSrcId: 1, qerhjFreeSpace(): free hash-join memory

    kxhfRemoveChunk: remove chunk 0 from slot table

    注意到上述显示内容中我粗体标出的部分,如“Number of in-memory partitions (may have changed): 8”、“Final number of hash buckets: 2048”、“Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799”、“Total number of rows: 1000”、“Maximum number of rows in a bucket: 4”、“Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000”等,这说明上述哈希连接驱动结果集的记录数为1000,共有8个Hash Partition、2048个Hash Bucket,这2048个Hash Bucket中有1249个是空的(即没有记录)、799个有记录,包含记录数最多的一个Hash Bucket所含记录的数量为4以及上述哈希连接并没有启用位图过滤。

    展开全文
  • Imports System Imports System.Security Imports System.Security.Cryptography Imports System.Text Public Class Form1 ... Private Sub btnMD5_Click1(ByVal sender As...比之一般的字符串连接方法效率更高。

    Imports System
    Imports System.Security
    Imports System.Security.Cryptography
    Imports System.Text

    Public Class Form1

        Private Sub btnMD5_Click1(ByVal sender As System.Object, _
        ByVal e As System.EventArgs) Handles btnMD5.Click
            Dim sSourceData As String
            Dim tmpSource() As Byte
            Dim tmpHash() As Byte

            sSourceData = Me.txtSource.Text
            'Create a byte array from source data.
            tmpSource = ASCIIEncoding.ASCII.GetBytes(sSourceData)

            'Compute hash based on source data.
            tmpHash = New MD5CryptoServiceProvider().ComputeHash(tmpSource)

            Me.txtMD5.Text = ByteArrayToString(tmpHash)

        End Sub

        Private Function ByteArrayToString(ByVal arrInput() As Byte) As String
            Dim i As Integer
            Dim sOutput As New StringBuilder(arrInput.Length)
            For i = 0 To arrInput.Length - 1
                sOutput.Append(arrInput(i).ToString("X2"))
            Next
            Return sOutput.ToString()
        End Function

        Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
            Debug.Print(Len(txtMD5.Text))
        End Sub
    End Class 

    提示

    计算 MD5 哈希值是用 MD5CryptoServiceProvider().ComputeHash 这个方法。

    由于 ComputeHash 方法需要传入的参数是 Byte 类型,而不是 String 类型。因此要将传入的数据先从字符串变成一个 Byte 数组。用 ASCIIEncoding.ASCII.GetBytes 这个函数,可以将一个字符串变成一个 Byte 数组。

    用 ComputeHash 方法计算并返回一个 MD5 哈希值,该返回值也是 Byte 类型。通常我们会将这个返回值变成一个 16 进制的字符串。上面代码中 ByteArrayToString 函数的作用,就是将一个 Byte 数组转换成一个 16 进制的字符串。

    StringBuilder.Append 方法进行字符串的连接。比之一般的字符串连接方法效率更高。

    展开全文
  • 哈希原理与常见哈希函数

    千次阅读 2020-01-09 18:11:06
    转换方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。 F(x)=rand() :每次返回一个随机值,是不好的哈希 (2)...

    一,什么是哈希

    哈希是将任意长度的数据转换为一个数字的过程。这个数字是在一个固定的范围之内的。
    转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。

    哈希函数

    1.哈希特点

    (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。

    F(x)=rand() :每次返回一个随机值,是不好的哈希
    

    (2)散列性:不同的值的哈希值尽量不同,理想情况下每个值对应于不同的数字。

    F(x)=1 : 不管输入什么都返回1,是不好的哈希
    
    2.冲突怎么解决

    把一个大的集合映射到一个固定大小的集合中,肯定是存在冲突的。这个是抽屉原理或者叫鸽巢理论。

    桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

    (1)拉链法:

    链表地址法是使用一个链表数组来存储相应数据,当hash遇到冲突的时候依次添加到链表的后面进行处理。Java里的HashMap是拉链法解决冲突的典型应用场景。

    Java8 HashMap

    Java8的HashMap中,使用一个链表数组来存储数据,根据元素的哈希值确定存储的数组索引位置,当冲突时,就链接到元素后面形成一个链表,Java8中当链表长度超过8的时候就变成红黑树以优化性能,红黑树也可以视为拉链法的一种变形。

    (2)开放地址法

    开放地址法是指大小为 M 的数组保存 N 个键值对,其中 M >N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表。

    线性探测法,就是比较常用的一种“开放地址”哈希表的一种实现方式。线性探测法的核心思想是当冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。简单来说就是:一旦发生冲突,就去寻找下 一个空的散列表地址,只要散列表足够大,空的散列地址总能找到。

    Java8中的HashTable就是用线性探测法来解决冲突的。

        public synchronized V put(K key, V value) {
            // Make sure the value is not null
            if (value == null) {
                throw new NullPointerException();
            }
    
            // Makes sure the key is not already in the hashtable.
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for(; entry != null ; entry = entry.next) {
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    
            addEntry(hash, key, value, index);
            return null;
        }
    
        private void addEntry(int hash, K key, V value, int index) {
            modCount++;
    
            Entry<?,?> tab[] = table;
            if (count >= threshold) {
                // Rehash the table if the threshold is exceeded
                rehash();
    
                tab = table;
                hash = key.hashCode();
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            // Creates the new entry.
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            tab[index] = new Entry<>(hash, key, value, e);
            count++;
        }
    
    

    (2)冲突解决示例

    举个例子,假如散列长度为8,哈希函数是:y=x%7。两种解决冲突的方式如下:

    拉链法解决冲突
    拉链法

    线性探测法解决冲突
    线性探测法

    二,几个常见哈希算法

    1.MD5

    MD5哈希算法是将任意字符散列到一个长度为128位的Bit数组中,得出的结果表示为一个32位的十六进制数字。

    MD5哈希算法有以下几个特点:

    1. 正像快速:原始数据可以快速计算出哈希值
    2. 逆向困难:通过哈希值基本不可能推导出原始数据
    3. 输入敏感:原始数据只要有一点变动,得到的哈希值差别很大
    4. 冲突避免:很难找到不同的原始数据得到相同的哈希值

    算法过程:

    1. 数据填充:

    将原数据的二进制值进行补齐。

    (1)填充数据:使得长度模除512后得到448,留出64个bit来存储原信息的长度。填充规则是填充一个1,后面全部是0。

    (2)填充长度数据:计算原数据的长度数据,填充到最后的64个bit上,如果消息长度数据大于64bit就使用低64位的数据。

    第一步:填充数据

    1. 迭代计算:

    将填充好的数据按照每份512的长度进行切分,对每一份依次进行处理,每份的处理方式是使用四个函数进行依次进行计算,每个函数都有四个输入参数,输出也是四个数字,输出的数字作为下一份数据的输入,所有份数的数据处理完毕,得到的四个数字连接起来就是最终的MD5值。

    以下图片是整个迭代计算的过程示意图,其中四个初始参数和四个函数定义如下:

    //四个初始参数值
    A=0x67452301;
    B=0xefcdab89;
    C=0x98badcfe;
    D=0x10325476;
    
    //四个函数的定义
    // a、b、c、d是每次计算时候的四个参数
    F=(b&c)|((~b)&d);
    F=(d&b)|((~d)&c);
    F=b^c^d;
    F=c^(b|(~d));
    

    第二步:数据计算

    1. md5的java实现
    package com.chybin.algorithm.chapter2;
    
    /**
     * Create By 鸣宇淳 on 2019/12/26
     **/
    public class MD5{
        /*
         *四个链接变量
         */
        private final int A=0x67452301;
        private final int B=0xefcdab89;
        private final int C=0x98badcfe;
        private final int D=0x10325476;
        /*
         *ABCD的临时变量
         */
        private int Atemp,Btemp,Ctemp,Dtemp;
    
        /*
         *常量ti
         *公式:floor(abs(sin(i+1))×(2pow32)
         */
        private final int K[]={
                0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
                0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8,
                0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,
                0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51,
                0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
                0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,
                0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,
                0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,
                0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
                0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244,
                0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
                0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,
                0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
        /*
         *向左位移数,计算方法未知
         */
        private final int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7,
                12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
                4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10,
                15,21,6,10,15,21,6,10,15,21,6,10,15,21};
    
    
        /*
         *初始化函数
         */
        private void init(){
            Atemp=A;
            Btemp=B;
            Ctemp=C;
            Dtemp=D;
        }
        /*
         *移动一定位数
         */
        private    int    shift(int a,int s){
            return(a<<s)|(a>>>(32-s));//右移的时候,高位一定要补零,而不是补充符号位
        }
        /*
         *主循环
         */
        private void MainLoop(int M[]){
            int F,g;
            int a=Atemp;
            int b=Btemp;
            int c=Ctemp;
            int d=Dtemp;
            for(int i = 0; i < 64; i ++){
                if(i<16){
                    F=(b&c)|((~b)&d);
                    g=i;
                }else if(i<32){
                    F=(d&b)|((~d)&c);
                    g=(5*i+1)%16;
                }else if(i<48){
                    F=b^c^d;
                    g=(3*i+5)%16;
                }else{
                    F=c^(b|(~d));
                    g=(7*i)%16;
                }
                int tmp=d;
                d=c;
                c=b;
                b=b+shift(a+F+K[i]+M[g],s[i]);
                a=tmp;
            }
            Atemp=a+Atemp;
            Btemp=b+Btemp;
            Ctemp=c+Ctemp;
            Dtemp=d+Dtemp;
    
        }
        /*
         *填充函数
         *处理后应满足bits≡448(mod512),字节就是bytes≡56(mode64)
         *填充方式为先加一个0,其它位补零
         *最后加上64位的原来长度
         */
        private int[] add(String str){
            int num=((str.length()+8)/64)+1;//以512位,64个字节为一组
            int strByte[]=new int[num*16];//64/4=16,所以有16个整数
            for(int i=0;i<num*16;i++){//全部初始化0
                strByte[i]=0;
            }
            int    i;
            for(i=0;i<str.length();i++){
                strByte[i>>2]|=str.charAt(i)<<((i%4)*8);//一个整数存储四个字节,小端序
            }
            strByte[i>>2]|=0x80<<((i%4)*8);//尾部添加1
            /*
             *添加原长度,长度指位的长度,所以要乘8,然后是小端序,所以放在倒数第二个,这里长度只用了32位
             */
            strByte[num*16-2]=str.length()*8;
            return strByte;
        }
        /*
         *调用函数
         */
        public String getMD5(String source){
            init();
            int strByte[]=add(source);
            for(int i=0;i<strByte.length/16;i++){
                int num[]=new int[16];
                for(int j=0;j<16;j++){
                    num[j]=strByte[i*16+j];
                }
                MainLoop(num);
            }
            return changeHex(Atemp)+changeHex(Btemp)+changeHex(Ctemp)+changeHex(Dtemp);
    
        }
        /*
         *整数变成16进制字符串
         */
        private String changeHex(int a){
            String str="";
            for(int i=0;i<4;i++){
                str+=String.format("%2s", Integer.toHexString(((a>>i*8)%(1<<8))&0xff)).replace(' ', '0');
    
            }
            return str;
        }
        /*
         *单例
         */
        private static MD5 instance;
        public static MD5 getInstance(){
            if(instance==null){
                instance=new MD5();
            }
            return instance;
        }
    
        private MD5(){};
    
        public static void main(String[] args){
            String str=MD5.getInstance().getMD5("123");
            System.out.println(str);
        }
    }
    
    2.SHA

    SHA类似MD5,也是一种信息摘要算法,也是将任意长度的字符串转换为固定长度的数字的算法。SHA算法是一个家族,有五个算法:SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512。这些变体除了生成摘要的长度、循环运行的次数等一些微小差异外,算法的基本结构是一致的。

    SHA-1算法的结果是一个160个bit的数字,比MD5的128个bit要长32位,碰撞几率要低了2^32倍。可是SHA-1和MD5一样已经被人破解,已经不安全了。

    SHA-256从名字上看就表明了它的值存储在长度为256的bit数组中的,SHA-512信息摘要长度是512个bit。

    SHA-224是SHA256的精简版本,SHA-384是SHA-512的精简版本,精简版本主要用在安全等级要求不太高的场景,比如只是验证下文件的完整性。使用什么版本的SHA取决于安全要求和算法速度,毕竟长度越长算法计算时间约长,但是安全等级高。

    在这里插入图片描述

    SHA算法过程:

    SHA算法的底层原理和MD5很相似,只是在摘要分段和处理细节上有少许差别,他们都是第一步将原数据进行填充,填充到512的整数倍,填充的信息包括10数据填充和长度填充,第二步切分为相同大小的块,第三步进行对每一块迭代,每块进行N轮运算,最终得到的值拼接起来就是最终的哈希值。

    以下是MD5、SHA-1、SHA-2系列的算法过程比较:

    MD5算法过程示意图:

    MD5是对每一块数据分为四个部分,用四个函数进行运算。最终生成128位的哈希值。

    MD5算法过程

    SHA-1算法过程示意图:

    SHA-1是将每一块数据分为五个部分。

    SHA-1算法过程

    SHA-2算法过程示意图:

    SHA-2是分为八个部分,算法也更加复杂。

    SHA-2算法过程

    3.SimHash

    SimHash是Google提出的一种判断文档是否重复的哈希算法,他是将文本转换为一个64位的哈希值,然后计算两个哈希值的距离,如果小于n(n一般是3)就认为这两个文本是相似的。

    之所以能够这样判断是否相似是因为SimHash算法不同于MD5之类的算法,SimHash算法是局部敏感的哈希算法,MD5算法是全局敏感的哈希算法。在MD5中原数据只要有一个字符的变化,哈希值就会变化很大,而在SimHash算法中,原数据变化一小部分,哈希值也只有很小一部分的变化,所以只要哈希值很类似,就意味着原数据就很类似。

    算法实现:

    参考这个博客【[Algorithm] 使用SimHash进行海量文本去重】

    (1)第一步:哈希

    1. 分词: 将文本进行分词,并给单词分配权重。
    2. hash: 对每个次进行hash计算,得到哈希值。
    3. 加权: 对每个单词的has进行加权。
    4. 合并: 把上一步加权hash值合并累计起来。
    5. 降维: 把上一步累加起来的值变为01。如果每一位大于0 记为 1,小于0 记为 0。

    (2)第二步:计算海明距离

    两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。

    举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。

    异或就是如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。两个simhash值进行异或,得出的结果中1的个数就是海明距离。

    simhash计算过程

    判断两个文本是否相似,就计算两个simhash哈希值的海明距离,根据经验,如果海明距离小于3就可以判定两个文本是相似的。

    4.GeoHash

    GeoHash 算法将经纬度哈希为一个数字,然后将数字base32编码为一个字符串。

    比如:北海公园的经纬度是:(39.928167,116.389550),对应的GeoHash值可以为wx4g、wx4g0、wx4g0s、wx4g0s8、wx4g0s8q。GeoHash值代表的是这个经纬度点所在的一个矩形区域,长度越长矩形面积约小,表示的越精确。

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    两个位置的GeoHash值前部分一样的位数越多,说明两个位置离得越近,百度地图的查找附近、滴滴打车查找附近的车辆功能就可以使用这个算法。

    GeoHash算法过程

    下面对于北海公园的经纬度(39.928167,116.389550)进行编码,了解下算法过程。

    (1)第一步:纬度编码

    将整个地球从水平方向上进行逐步切分,确定纬度39.928167在哪个区域中。

    纬度范围是-90到90,每次平均分为两份,进行逐步细化地迭代。

    1. 第一次迭代:处于-90到0的标记为0,0到90的标记为1,39.928167处于1的区间,所以最终结果的第一位是1。
    2. 第二次迭代:对上一步标记为1的部分平分,0到45标记为0,45到90标记为1,39.928167标记为1处于0的区间,所以最终结果的第二位是0。
    3. 第三次迭代:对上一步标记为0的部分平分,0到22.5标记为0,22.5到45标记为1,39.928167标记为1处于0的区间,所以最终结果的第三位是0
    4. 第四次迭代:对上一步标记为0的部分平分,22.5到33.75标记为0,33.75到45标记为1,39.928167标记为1处于1的区间,所以最终结果的第三位是1。

    经过N次迭代后,得到一个长度为N的二进制值,比如得到的值为1011100011,这个就是对纬度进行的编码最终值。

    纬度编码示意图

    (2)第二步:经度编码

    对经度的编码过程跟对纬度编码过程十分类似,不同点是经度范围是-180到180,对经度116.389550经过N次迭代后得到编码值。比如得到1101001011。这个就是对经度编码的最终值。

    (3)第三步:合并经纬度

    对纬度编码值、经度编码值进行合并,合并规则是奇数位放纬度、偶数位放经度,合并为一个新的二进制串。

    (4)第四步:转换为字符串

    将上一步合并的二进制11100 11101 00100 01111每5位一段转换为十进制,结果是28、29、4、15,Base32编码后为wx4g。这个就是北海公园的经纬度(39.928167,116.389550)最终的GeoHash编码值。

    以下图表是二进制数字、base32字符对应表:

    Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    Base 32 0 1 2 3 4 5 6 7 8 9 b c d e f
    Decimal 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
    Base 32 h j k m n p q r s t u v w x y
    展开全文
  • hash join (Oracle里的哈希连接原理)

    千次阅读 2015-09-25 17:00:28
    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。 在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法...

    哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

    在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷。对于排序合并连接,如果两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。

    为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,Oracle在Oracle 7.3中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。

    在Oracle 10g及其以后的Oracle数据库版本中,优化器(实际上是CBO,因为哈希连接仅适用于CBO)在解析目标SQL时是否考虑哈希连接是受限于隐含参数_HASH_JOIN_ENABLED,而在Oracle 10g以前的Oracle数据库版本中,CBO在解析目标SQL时是否考虑哈希连接是受限于参数HASH_JOIN_ENABLED。

    _HASH_JOIN_ENABLED的默认值是TRUE,表示允许CBO在解析目标SQL时考虑哈希连接。当然,即使你将该参数的值改成了FALSE,我们使用USE_HASH Hint依然可以让CBO在解析目标SQL时考虑哈希连接,这说明USE_HASH Hint的优先级高于参数_HASH_JOIN_ENABLED。

       

    如果两个表(这里将它们分别命名为表T1和表T2)在做表连接时使用的是哈希连接,则Oracle在做哈希连接时会依次顺序执行如下步骤:

    1、  首先Oracle会根据参数HASH_AREA_SIZE、DB_BLOCK_SIZE和_HASH_MULTIBLOCK_IO_COUNT的值来决定Hash Partition的数量(Hash Partition是一个逻辑上的概念,所有Hash Partition的集合就被称之为Hash Table,即一个Hash Table是由多个Hash Partition所组成,而一个Hash Partition又是由多个Hash Bucket所组成);

    2、  表T1和T2在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集会被Oracle选为哈希连接的驱动结果集,这里我们假设T1所对应的结果集的数据量相对较小,我们记为S;T2所对应的结果集的数据量相对较大,我们记为B;显然这里S是驱动结果集,B是被驱动结果集;

    3、  接着Oracle会遍历S,读取S中的每一条记录,并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算,这个哈希运算会使用两个内置哈希函数,这两个哈希函数会同时对该连接列计算哈希值,我们把这两个内置哈希函数分别记为hash_func_1和hash_func_2,它们所计算出来的哈希值分别记为hash_value_1和hash_value_2;

    4、  然后Oracle会按照hash_value_1的值把相应的S中的对应记录存储在不同Hash Partition的不同Hash Bucket里,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值。注意,存储在Hash Bucket里的记录并不是目标表的完整行记录,而是只需要存储位于目标SQL中的跟目标表相关的查询列和连接列就足够了;我们把S所对应的每一个Hash Partition记为Si;

    5、  在构建Si的同时,Oracle会构建一个位图(BITMAP),这个位图用来标记Si所包含的每一个Hash Bucket是否有记录(即记录数是否大于0)

    6、  如果S的数据量很大,那么在构建S所对应的Hash Table时,就可能会出现PGA的工作区(WORK AREA)被填满的情况,这时候Oracle会把工作区中现有的Hash Partition中包含记录数最多的Hash Partition写到磁盘上(TEMP表空间);接着Oracle会继续构建S所对应的Hash Table,在继续构建的过程中,如果工作区又满了,则Oracle会继续重复上述挑选包含记录数最多的Hash Partition并写回到磁盘上的动作;如果要构建的记录所对应的Hash Partition已经事先被Oracle写回到了磁盘上,则此时Oracle就会去磁盘上更新该Hash Partition,即会把该条记录和hash_value_2直接加到这个已经位于磁盘上的Hash Partition的相应Hash Bucket中;注意,极端情况下可能会出现只有某个Hash Partition的部分记录还在内存中,该Hash Partition的剩余部分和余下的所有Hash Partition都已经被写回到磁盘上

    7、  上述构建S所对应的Hash Table的过程会一直持续下去,直到遍历完S中的所有记录为止;

    8、  接着,Oracle会对所有的Si按照它们所包含的记录数来排序,然后Oracle会把这些已经排好序的Hash Partition按顺序依次、并且尽可能的全部放到内存中(PGA的工作区),当然,如果实在放不下的话,放不下的那部分Hash Partition还是会位于磁盘上。我认为这个按照Si的记录数来排序的动作不是必须要做的,因为这个排序动作的根本目的就是为了尽可能多的把那些记录数较小的Hash Partition保留在内存中,而将那些已经被写回到磁盘上、记录数较大且现有内存已经放不下的Hash Partition保留在磁盘上,显然,如果所有的Si本来就都在内存中,也没发生过将Si写回到磁盘的操作,那这里根本就不需要排序了

    9、     至此Oracle已经处理完S,现在可以来开始处理B了;

    10、 Oracle会遍历B,读取B中的每一条记录,并对B中的每一条记录按照该记录在表T2中的连接列做哈希运算,这个哈希运算和步骤3中的哈希运算是一模一样的,即这个哈希运算还是会用步骤3中的hash_func_1和hash_func_2,并且也会计算出两个哈希值hash_value_1和hash_value_2;接着Oracle会按照该记录所对应的哈希值hash_value_1去Si里找匹配的Hash Bucket;如果能找到匹配的Hash Bucket,则Oracle还会遍历该Hash Bucket中的每一条记录,并会校验存储于该Hash Bucket中的每一条记录的连接列,看是否是真的匹配(即这里要校验S和B中的匹配记录所对应的连接列是否真的相等,因为对于Hash运算而言,不同的值经过哈希运算后的结果可能是一样的),如果是真的匹配,则上述hash_value_1所对应B中的记录的位于目标SQL中的查询列和该Hash Bucket中的匹配记录便会组合起来,一起作为满足目标SQL连接条件的记录返回;如果找不到匹配的Hash Bucket,则Oracle就会去访问步骤5中构建的位图,如果位图显示该Hash Bucket在Si中对应的记录数大于0,则说明该Hash Bucket虽然不在内存中,但它已经被写回到了磁盘上,则此时Oracle就会按照上述hash_value_1的值把相应B中的对应记录也以Hash Partition的方式写回到磁盘上,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值;如果位图显示该Hash Bucket在Si中对应的记录数等于0,则Oracle就不用把上述hash_value_1所对应B中的记录写回到磁盘上了,因为这条记录必然不满足目标SQL的连接条件;这个根据位图来决定是否将上述hash_value_1所对应B中的记录写回到磁盘的动作就是所谓的“位图过滤”我们把B所对应的每一个Hash Partition记为Bj

    11、 上述去Si中查找匹配Hash Bucket和构建Bj的过程会一直持续下去,直到遍历完B中的所有记录为止;

    12、 至此Oracle已经处理完所有位于内存中的Si和对应的Bj,现在只剩下位于磁盘上的Si和Bj还未处理;

    13、 因为在构建Si和Bj时用的是同样的哈希函数hash_func_1和hash_func_2,所以Oracle在处理位于磁盘上的Si和Bj的时候可以放心的配对处理,即只有对应Hash Partition Number值相同的Si和Bj才可能会产生满足连接条件的记录;这里我们用Sn和Bn来表示位于磁盘上且对应Hash Partition Number值相同的Si和Bj

    14、 对于每一对儿Sn和Bn,它们之中记录数较少的会被当作驱动结果集,然后Oracle会用这个驱动结果集的Hash Bucket里记录的hash_value_2来构建新的Hash Table,另外一个记录数较大的会被当作被驱动结果集,然后Oracle会用这个被驱动结果集的Hash Bucket里记录的hash_value_2去上述构建的新Hash Table中找匹配记录;注意,对每一对儿Sn和Bn而言,Oracle始终会选择它们中记录数较少的来作为驱动结果集,所以每一对儿Sn和Bn的驱动结果集都可能会发生变化,这就是所谓的“动态角色互换”

    15、 步骤14中如果存在匹配记录,则该匹配记录也会作为满足目标SQL连接条件的记录返回;

    16、 上述处理Sn和Bn的过程会一直持续下去,直到遍历完所有的Sn和Bn为止。

     

    对于哈希连接的优缺点及适用场景,我们有如下总结:

    Ÿ     哈希连接不一定会排序,或者说大多数情况下都不需要排序;

    Ÿ     哈希连接的驱动表所对应的连接列的可选择性应尽可能的好,因为这个可选择性会影响对应Hash Bucket中的记录数,而Hash Bucket中的记录数又会直接影响从该Hash Bucket中查找匹配记录的效率;如果一个Hash Bucket里所包含的记录数过多,则可能会严重降低所对应哈希连接的执行效率,此时典型的表现就是该哈希连接执行了很长时间都没有结束,数据库所在database server上的CPU占用率很高,但目标SQL所消耗的逻辑读却很低,因为此时大部分时间都耗费在了遍历上述Hash Bucket里的所有记录上,而遍历Hash Bucket里记录这个动作是发生在PGA的工作区里,所以不耗费逻辑读

    Ÿ     哈希连接只适用于CBO、它也只能用于等值连接条件(即使是哈希反连接,Oracle实际上也是将其转换成了等价的等值连接)

    Ÿ     哈希连接很适合于一个小表和大表之间的表连接,特别是在小表的连接列的可选择性非常好的情况下,这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当

    Ÿ     当两个表做哈希连接时,如果这两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集所对应的Hash Table能够完全被容纳在内存中时(PGA的工作区),则此时的哈希连接的执行效率会非常高。

    来源: http://www.dbsnake.com/oracle-hash-join.html

    展开全文
  • 哈希算法

    千次阅读 2014-05-06 16:03:04
    哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生...
  • 嵌套,合并,哈希 连接原理

    千次阅读 2009-05-19 13:43:00
    在许多小事务中(如那些只影响较小的一组行的事务),索引嵌套循环联接优于合并联接和哈希联接。但在大型查询中,嵌套循环联接通常不是最佳选择。   2.   合并联接 合并联接要求两个输入都...
  • 哈希算法简介

    2020-09-11 13:15:39
    哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生...
  • 在ORACLE数据库中,两个表之间的表连接方法有合并排序连接,嵌套循环连接,哈希连接和笛卡尔连接这四种,这四种表连接方法各有优缺点。下面分别来简单介绍下。
  • 综述:深度哈希方法 摘要 最近邻搜索是寻找数据库中的数据点,使它们到查询的距离最小,这是计算机视觉、推荐系统和机器学习等各个领域的一个基本问题。哈希是计算效率和存储效率最广泛使用的方法之一。随着深度学习...
  • 哈希检索

    2017-03-13 09:27:26
     LSH是Locality Sensitive Hashing的缩写,也翻译为局部敏感哈希,是一种通过设计满足特殊性质即局部敏感的哈希函数,提高相似查询效率的方法。虽然从正式提出距今不过十余年,由于其局部敏感的特殊性质,以及在...
  • 密码学之哈希算法

    千次阅读 2018-09-11 21:41:48
    哈希算法是将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将...
  • 哈希文件

    千次阅读 2011-12-17 00:35:47
    在大多数查找方法中(如顺序查找、折半查找、分块查找等),其查找的过程中都需要依据关键字进行若干次的比较判断,最后确定在数据集合中是否存在关键字等于某个给定的记录以及该记录在数据所形成的表中的位置,...
  • 增加桶式的动态哈希

    千次阅读 2014-10-20 10:28:27
    哈希值的获取字符串的二进制,再二进制转换为一组数字,这组数字就是用来确定key在哪个桶层中的 代码中 #define tongsize 8 //桶大小是2的n次方,,,,,这里的n=3(2的3次方等于8),那么会把3个二进制转换为一个...
  • 哈希算法 MD5

    千次阅读 2012-10-15 14:58:40
     用来产生一些数据片段(例如消息或会话项)的哈希值的算法。使用好的哈希算法,在输入数据中所做的更改就可以更改结果哈希值中的所有位;因此,哈希对于检测数据对象(例如消息)中的修改很有用。此外,好的哈希...
  • 哈希表详解

    千次阅读 2016-05-11 19:58:10
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而...给定表M,存在函数f(key),对任意给定的关键字key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈
  • 哈希算法将任意长度的二进制值映射为固定长度的较小二进制值,这个小的二进制值称为哈希值哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的哈希都将产生...
  • 哈希

    2012-06-22 10:11:10
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的...
  • 哈希表的特点:关键字在表中的位置和它之间不存在一个确定的关系,查找的过程为给定一次和各个关键字进行比较,查找的效率取决于和给定进行比较的次数。  哈希表的特点:关键字在表中位置和它之间存在一种...
  • 基于哈希函数的签名

    千次阅读 2019-05-13 18:28:28
    不过,现在 Merkle 方法主要的公钥只是一串简单的哈希值,使得这个方法比上面提到的原始 Lamport 方法更为简洁。 最后还有个优化部分,密码学强度的 伪随机数发生器 能够输出生成各式各样的密钥,同时“压缩”...
  • 哈希表简介

    2013-12-22 19:58:18
    这种转换是一种压缩映射,也就是,散列的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列来唯一的确定输入。简单的说就是一种将任意长度的消息压缩到某一固定长度的消
  • 近期在contented based召回模块寻找相似商品时牵扯到大量计算,内存和耗时都是不可接受的,于是查找了多篇文章,找到了spark的LSH方法,示例代码写的很简单,这里有一篇uber的实践,写得很详细,特转载,仅供个人...
  • 基本数据类型和包装类、String类的转换&toString方法&instanceof运算符1.包装类
  • 深度哈希-DHN

    千次阅读 2017-03-08 19:33:54
    Deep Hashing Network for Efficient Similarity Retrieval AAAI 2016 源码:https://github.com/zhuhan1236/dhn-caffe与上一篇文章类似,通过设计损失函数,使得最后全连接... 哈希方法的目标是得到二编码,所以优
  • 什么是哈希

    千次阅读 2014-02-17 17:45:57
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)...给定表M,存在函数f(key),对任意给定的关键字key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希
  • 今天下午使用ssh连接其他服务器进行scp操作的时候,提示失败,如下所示: [root@localhost backups]# scp root@172.xxx.xxx.xxx:/data/gitlabData/backups/1539717714_2018_10_17_9.4.3_gitlab_backup.tar . @@@...
  • java 哈希

    千次阅读 2014-08-05 10:01:13
    哈希码产生的依据:哈希码并不是完全唯一的,它是一种算法,让同一个类的对象按照自己不同的特征尽量的有不同的哈希码,但不表示不同的对象哈希码完全不同。也有相同的情况,看程序员如何写哈希码的算法。
  • 局部敏感哈希

    千次阅读 2016-01-21 22:47:10
    局部敏感哈希 在检索技术中,索引一直需要研究的核心技术。当下,索引技术主要分为三类:基于树的索引技术(tree-based index)、基于哈希的索引技术(hashing-based index)与基于词的倒排索引(visual words ...
  • 1.1 密码学哈希函数

    2018-09-12 15:13:01
    ● 它产生固定大小的输出。为使本章讨论更具体,我们假设输出值大小为256位,但是,我们的讨论适用于任意规模的输出,只要其足够大。● 它能进行有效计算,简单来说...更准确地说,对应n位的字符串,其哈希值计算...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,928
精华内容 21,171
关键字:

哈希值转换链接方法