精华内容
下载资源
问答
  • 在页式存储管理方式中,如果没有引入,则每取数据,要访问()次内存 ; 段页式存储管理方式中,如果没有引入,则每取数据,要访问()次内存?
  • 数组也是有一定的缺点的,如果我们不知道某个元素的下标值,而只是知道该元素在数组中,这时我们想要获取该元素就只能对数组进行线性查找,即从头开始遍历,...所以,为了解决上述数组的不足之处,引入了哈希的概念。

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    数组是我们平时常见的并且经常使用的一种数据结构,那么它具有什么优点呢?我们都知道,在我们知道数组中某元素的下标值时,我们可以通过下标值的方式获取到数组中对应的元素,这种获取元素的速度是非常快的。

    但是呢,数组也是有一定的缺点的,如果我们不知道某个元素的下标值,而只是知道该元素在数组中,这时我们想要获取该元素就只能对数组进行线性查找,即从头开始遍历,这样的效率是非常低的,如果一个长度为10000的数组,我们需要的元素正好在第10000个,那么我们就要对数组遍历10000次,显然这是不合理的。

    所以,为了解决上述数组的不足之处,引入了哈希表的概念,哈希表在很多语言的底层用到的非常的多,本文我们将来讲解一下哈希表。因为哈希表的底层知识很多,但是代码是非常简洁的,所以请大家耐心看完。

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    一、什么是哈希表

    文章开头就说了,哈希表可以弥补数组的一些缺点,所以我们就可以在数组的基础上做一些改动,来实现哈希表。

    我们还是先以一个具体的例子来理解一下哈希表。

    假如图书馆有十万本图书,图书管理员把它们随意地放置在书架上,到数组中就是这个样子的
    在这里插入图片描述
    此时书架上的书是无序的,突然有一个同学说我要来找 《零基础入门JavaScript》 这本书,那么他们只能从书架上的第一本书开始挨个往后找,直到找到这本书为止。

    这就像数组中要找一个不知道下标的元素,只能遍历整个数组,这样不太好。

    那么有人就要说了,那我们在将图书放置到书架上的时候,给每一本书一个下标不就好了吗?到时候找书的时候直接通过下标来找到书,这样岂不是很方便?

    这话说的没错,我们平时去图书馆借书的时候,都是通过计算机来查询到一本书的编号,然后再去指定书架上找书的,那么在你查阅计算机时,计算机难道要遍历整个图书库,然后找到你要的那本书吗?这显然是不可能的,所以我们要研究出一种让计算机拿到一本书的名字时,就能得知这本书的编号的数据结构,这里就引入了哈希表的概念

    为了方便我们了我们先决定一个可接受的数组长度,比如说设置数组长度为10
    在这里插入图片描述
    然后把每本书的书名看作是一个字符串,例如 "零基础入门JavaScript",此时该字符串的长度为15,我们就分别获取每一个字符的Unicode 编码,然后用著名的秦九韶算法来将每一个Unicode 编码组合成一个很大的数。

    这里先来介绍一下 秦九韶算法。秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法,在西方被称作霍纳算法

    这是一个一元n次多项式的求和公式,我们可以看到,在这个公式中,一共有n次加法和(n+1)*n/2次乘法
    在这里插入图片描述
    而秦九韶算法就是对该公式进行了提取公因式,最终将式子变成这样
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    看到最终结果,我们可以看到,这个式子被简化以后,只需要进行n次乘法计算和n次加法计算了。

    这样的简化过程也为计算机处理多项式的求值问题提供了很大的便利,大幅度提高了求值的效率。这也就是我们为何要使用秦九韶算法来将字符串的Unicode 编码组合成一个很大的数的原因了。

    我们通过查阅 零基础入门JavaScript 中每个字符串的Unicode 编码,它们分别为 38646225223078420837383767497118978399114105112116

    然后我们把这些Unicode 编码代入到秦九韶算法中,得到 3.539723283210537e+26,这是一个特别特别特别大的数字,你可能想问,我们获得这么大的数干什么呢?因为我们刚才不是设定了数组的长度为10吗?所以我们将这个得到的数除以10取余,将获得的余数作为该元素在数组中的下标值。

    为什么要这么做呢?因为数组的长度为10,所以数组的下标值范围为0~9,那么一个数除以10取余,那么该余数的范围是不是也是0~9呢?那不正好跟数组的下标值对应起来了吗?
    在这里插入图片描述
    讲到这里了,我再来解释一下,为什么要通过秦九韶算法获取到一个这么大的数,然后再取余得到下标值呢?这不是多此一举么,为何不直接把每一个字符的Unicode 编码相加再直接取余,这样连乘法都不用算,全是加法,计算效率更高。那么我们再来看一个例子,就知道为何要用先获取一个很大的数了:

    首先,第一个字符串是 bcd,每个字符的Unicode 编码分别为 9899100,加起来等于297297 % 10 = 7,所以字符串 bcd 在数组中的下标值就为7;
    第二个字符串是 ace,每个字符的Unicode 编码分别为 9799101,加起来也等于297,所以同样的,ace 在数组中的下标值也同样为7;

    此时,两个字符串的下标值就重复了,这种现象在哈希表中称为冲突,在下文我会详细讲到。话说回来,就是因为简单的相加取余会很容易就出现冲突的现象,所以我们才选择利用秦九韶算法来给每个字符串规定相应的下标值,这样能在很大程度上保证了每个元素的下标值不重复,当然了也是会有一定几率重复的,这是不可避免的。
    在这里插入图片描述
    上面将一个字符串转化为数组长度范围内的下标值的过程就称作为 哈希化,而实现哈希化的代码一般会封装在一个函数里,这个函数就叫做 哈希函数

    按照上述所说的方法,对每本书的书名字符串进行哈希化,就可以使每本书获得一个下标值并存储在数组中了,之后当你要查阅一本书的编码时,你输入那本书的书名,计算机拿到以后,只需要通过哈希函数的处理,就可以获得这本书的下标值,然后瞬间获得这本书的编号。

    相信大家对 哈希表 应该有了一定的了解了,如果没看懂,我们下面再慢慢讲解。

    二、哈希表的优缺点

    在刚才哈希表的描述中,大家一定能看出哈希表的优缺点了,这里我来给大家总结一下吧~

    (1)优点

    首先是哈希表的优点:

    1. 无论数据有多少,处理起来都特别的快
    2. 能够快速地进行 插入修改元素删除元素查找元素 等操作
    3. 代码简单(其实只需要把哈希函数写好,之后的代码就很简单了)

    (2)缺点

    然后再来讲讲哈希表的缺点:

    1. 哈希表中的数据是没有顺序的
    2. 数据不允许重复

    三、冲突

    前面提到了冲突,其含义就是在哈希化以后有几个元素的下标值相同,这就叫做 冲突。 那当两个元素的下标值冲突时,是后一个元素是不是要替换掉前一个元素呢?当然不是!

    那么如何解决冲突这个现象呢?一般是有两种方法,即拉链法(链地址法)开放地址法

    (1)拉链法

    这种方法是很常用的解决冲突的方法。我们还是拿上面那个例子来说,10本图书通过哈希化以后存入到长度为10的数组当中,难免有几本书的下标值是相同的,那么我们可以将这两个下标值相同的元素存入到一个单独的数组中,然后将该数组存放在他们原本所在数组的下标位置,如图
    在这里插入图片描述
    假设图书1图书2 哈希化后的下标值都为3,那么我们就可以在原数组下标3的位置放一个数组,同时存放这两本图书。因此,无论是查询哪本图书,计算机获得的下标值都是3,然后再对这个位置的数组进行遍历即可获得想要的图书。

    这是第一种解决 冲突 的方法,但使用是还是需要考虑数组长度是否合适的,之后会进行讲解。

    (2)开放地址法

    这种方法简单来说就是当元素下标值发生冲突时,寻找空白的位置插入数据。假设当前下标值为1和3的位置分别已经插入了 图书3图书5,这时将 图书6 进行哈希化,发现它的下标值也是1,此时与 图书3 发生冲突,那么此时 图书6 就可以找到下一个空着的没插入元素的位置进行插入,如图
    在这里插入图片描述
    其实当发生冲突时,寻找空白的位置也有三种方法,分别是 线性探测二次探测再哈希法

    1. 线性探测

    顾名思义,线性探测的意思就是,当某两个元素发生冲突时,将当前索引+1,查看该位置是否为空,是的话就插入数据,否则就继续将索引+1,以此类推……直到插入数据位置。

    但这种方法有一个缺点,那就是当数组中连续很长的一个片段都已经插入了数据,此时用线性探测就显得效率没那么高了,因为每次探测的步长都为1,所以这段都已经插入了数据的片段都得进行探测一次,这种现象叫做 聚集。如下图,就是一个典型的聚集现象
    在这里插入图片描述
    图书8 的下标值为1,与 图书3 冲突,然后进行线性探测,依次经过 图书6、5、1、7 都没有发现有空白位置可以插入,直到末尾才找到空白位置插入,这样挺不好的,所以我们可以选用 二次探测 来缓解 聚集 这种现象。

    2. 二次探测

    二次探测 在线性探测的基础上,将每次探测的步长改为了当前下标值 index + 1²index + 2²index + 3² …… 直到找到空白位置插入元素为止

    还是举一个例子来理解一下 二次探测

    假如现在已存入 图书3图书5图书7,如图
    在这里插入图片描述
    然后此时要存入一个 图书6,通过哈希化以后求得的下标值为2,与 图书5 冲突了,所以就从索引2的位置向后再移动 个位置,但此时该位置上已存有数据,如下面这个动图演示
    在这里插入图片描述
    所以此时从索引为2的位置向后移动 个位置,此时发现移动后的位置上也已存有数据,所以仍无法插入数据,如下面这个动图演示
    在这里插入图片描述
    因此,我们继续从索引2的位置向后移动 个位置,此时发现,移动后的位置上有空余位置,于是直接在此插入数据,这样一个二次探测的过程就完成了,如下列动图演示
    在这里插入图片描述
    我们可以看到,二次探测 在一定程度上解决了 线性探测 造成的 聚集 问题,但是它却在另一种程度造成了一种聚集,就比如 …… 上的聚集。所以这种方式还是有点不太好。

    3. 再哈希法

    再哈希法 就是再将我们传入的值进行一次 哈希化,获得一个新的探测步数 step,然后按照这个步数进行探测,找到第一个空着的位置插入数据。这在很大的程度上解决了 聚集 的问题。

    既然要再进行哈希化获得一个探测的步数,那么这个哈希化的处理过程一定要跟第一次哈希化的处理过程不一样,这样才能确认一个合适的搜索步长,提高查找效率。

    这里,我们就不用担心如何写一个不一样的哈希函数了,给大家看一个公认的比较好的哈希函数:step = constant - (key % constant)

    其中,constant 是一个自己定的质数常量,且小于数组的容量; key 就是第一次哈希化得到得值。

    然后我们再通过这个函数算得的步长来进行查找搜索空位置进行插入即可,这里就不做过多的演示了。

    四、哈希表的扩容和减容

    在了解哈希表的扩容之前,我们来了解一个概念,叫做填充因子,它表示的是哈希表中的数据个数与哈希表长度的比值。其决定了哈希表的存取数据所需的时间大小。

    当我们用第一种解决冲突的办法——拉链法,填充因子最小为0,最大为无限大,这是因为该方法是通过在数组中的某个位置插入一个数组用来存储互相冲突的元素,因此,只要有可能,哈希表的长度可以很小,然后数据都存储在内置的数组中,这样填充因子就可以无限大了。

    那当我们用第二种解决冲突的办法——开放地址法,填充因子最小为0,最大只能为1,这是因为开放地址法的实现原理是找哈希表中空位置插入元素,因此哈希表中的数据量不会大于哈希表的长度,从而填充因子最大也只能是1。

    在这里插入图片描述

    把哈希表比作是个教室,如果教室里坐满了人,然后让你从中找出你的朋友,那密密麻麻的,是不是特别不好找,可能会眼花缭乱;但是如果这个教室里只坐了 2/3 或者 1/2 的人,那么人群看起来就没那么密密麻麻,那让你找到你的朋友也许会相对容易一点。

    也正因为这样的情况,我们可以在适当的时候根据填充因子的大小对哈希表的长度进行扩大,从而减小填充因子的大小,降低我们数据存取所耗费的时间。

    这里我们就将填充因子等于 0.75 作为哈希表扩容的临界点,同时会在后面封装哈希表的时候实现扩容

    当然,填充因子太小也是不合适地,所以我们也会在适当的地方添加减容功能,即将填充因子等于 0.25 作为哈希表减容的临界点。

    五、哈希表的方法

    老规矩,我们在封装哈希表之前,先来看看哈希表常见的方法都有哪些

    方法含义
    put()向哈希表中插入数据或修改哈希表中数据
    get()获取哈希表中的某个数据
    del()删除哈希表中某个数据
    isEmpty()判断哈希表是否为空
    size()返回哈希表内元素个数
    resize()改变哈希表容量,并将数据放到正确的位置上
    isPrime()判断某个数是不是质数
    toPrime()获取离某个数最近的质数

    六、用代码实现哈希表

    前提:

    1. 本文选用链地址法解决冲突问题
    2. 涉及到常量的地方,都选用质数,例如哈希表容量 、霍纳算法的常量等。因为在数论上,使用质数可以尽可能地使数据在哈希表中均匀分布

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放哈希表的一些属性和方法。

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    }
    

    因为我们是通过数组来实现的哈希表,所以设置了属性 storage 来存储数据;然后定义了属性 count 用于统计哈希表内的数据个数,方便之后用于计算填充因子;最后定义了属性 length 设定了哈希表的初始长度为质数7

    (2)封装哈希函数

    在文章的开头,我就用霍纳算法讲解了哈希化的过程,因此我们在封装哈希函数时,就也通过霍纳算法的最终化简结构来实现

    这里,我放上霍纳算法的化简结果,方便大家观看学习

    P(n) = a 0 a_0 a0 + x( a 1 a_1 a1+x( a 2 a_2 a2 +…+ x( a n a_n an − 1 + x a n a_n an) ) )

    我们来看一下代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    }
    

    这里的霍纳算法中的常数我就随便取了一个质数37,大家也可以随便选别的稍微大一点的质数

    哈希函数接收两个参数,第一个参数为 str ,即我们之后传入数据的 key ;第二个参数为 size ,即哈希表的长度,所以可以直接进行调用我们设定的属性 this.length

    (3)实现put()方法(不具备扩容功能)

    put()方法就是向哈希表插入数据或者修改哈希表中某数据。

    该方法接收两个参数,第一个参数为 key;第二个参数为 value 。即相当于传入一个键值对

    实现思路:

    1. 通过哈希函数,将 key 哈希化,获取一个索引 index
    2. 判断哈希表 storage 数组的索引 index 上有无数据,若无,则直接在该位置上创建一个空数组 arr,并把我们传入的键值对打包放到一个新的数组中存到 arr
    3. 若有数据,则遍历该索引上的数组每个元素,比对每个元素的 key 是否与我们传入的 key 相等,若有查询到相等的值,则用我们传入的 value 替换查询到的该元素中的 value ,这就实现了修改数据的功能
    4. 若没有查询到相等的值,则直接将我们的键值对打包放到一个新的数组中存储到哈希表 index 索引上的数组中去,此时 this.count + 1

    为了方便大家理解,我用动图来给大家演示该方法的实现过程

    首先是插入数据操作
    在这里插入图片描述
    接下来是修改数据操作

    在这里插入图片描述

    我们来看一下代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	// 插入或修改数据
        HashTable.prototype.put = function (key, value) {
            // 1.哈希化获得下标值
            let index = this.hashFunc(key, this.length)
            let current = this.storage[index]
    
            // 2.判断该下标值的位置是否有数据
            // 2.1无数据
            if(!current) {
                this.storage[index] = [[key, value]]
                this.count ++
                return;
            }
            
    		// 2.2有数据
    		// 3.遍历对应索引上的数组
            for (let i = 0; i < current.length; i ++) {
                // 3.1已存在相同数据
                if(current[i][0] === key) {
                    current[i][1] = value
                    return;
                }
            }
            
            // 3.2未存在相同数据,直接添加数据
            current.push([key, value])
            this.count ++
        }
    }
    

    我们来使用一下该方法

    let ht = new HashTable()
    
    // 执行put()方法6次
    ht.put('abc', '123')
    ht.put('hgf', '124')
    ht.put('wds', '125')
    ht.put('wer', '126')
    ht.put('kgl', '127')
    ht.put('kmg', '128')
    
    // 查看哈希表内数据个数
    console.log(ht.count)              // 6
    
    // 通过storage属性查看一下哈希表的内部结构
    console.log(ht.storage)
    
    /* storage打印结果
    [
      [ [ 'wds', '125' ], [ 'kgl', '127' ], [ 'kmg', '128' ] ],
      [ [ 'wer', '126' ] ],
      <1 empty item>,
      [ [ 'hgf', '124' ] ],
      [ [ 'abc', '123' ] ]
    ]
    */
    

    此时的哈希表内部是这样的
    在这里插入图片描述

    (4)实现get()方法

    get()方法是用于查询哈希表中某个数据。该方法直接收一个参数,即用于查询的 key

    实现思路:

    1. 通过哈希函数,将 key 哈希化,获取一个索引 index
    2. 判断哈希表 storage 数组的索引 index 上有无数据,若无,则返回 false
    3. 若有数据,则遍历该索引上的数组每个元素,比对每个元素的 key 是否与我们传入的 key 相等,若有查询到相等的值,则返回该值的 value
    4. 若无数据,则返回 false

    思路和代码都比较简单,我们直接来看代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	// 获取数据
        HashTable.prototype.get = function (key) {
            // 1.获取相应的下标值
            let index = this.hashFunc(key, this.length)
            let current = this.storage[index]
    		
    		// 2.判断该下标值的位置是否有数据
            // 2.1 若该下标值位置不存在任何数据,则查找失败
            if(!current) {
                return false
            }
    
            // 2.2 该下标值位置有数据
            // 3. 进行遍历查找
            for(let i in current) {
                // 3.1 找到对应数据并返回value
                if(current[i][0] === key) {
                    return current[i][1]
                }
            }
    
            // 3.2 没有找到对应数据,返回false
            return false
        }
    }
    

    我们来使用以下该方法

    let ht = new HashTable()
    
    // 执行put()方法 6次
    ht.put('abc', '123')
    ht.put('hgf', '124')
    ht.put('wds', '125')
    ht.put('wer', '126')
    ht.put('kgl', '127')
    ht.put('kmg', '128')
    
    // 执行get()方法,获取 key为 'hgf' 的值
    console.log(ht.get('hgf'))           // 124
    

    (5)实现del()方法(不具备减少容量功能)

    del()方法是删除哈希表中某个数据。该方法接收一个参数 key

    实现思路:

    1. 通过哈希函数,将 key 哈希化,获取一个索引 index
    2. 判断哈希表 storage 数组的索引 index 上有无数据,若无,则返回 false ,表示删除失败
    3. 若有数据,则遍历该索引上的数组每个元素,比对每个元素的 key 是否与我们传入的 key 相等,若有查询到相等的值,则直接删除该值,此时 this.count --,并返回被删除元素的 value
    4. 若没有查询到相等的值,则返回 false ,表示删除失败

    我们来看一下代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	// 删除数据
        HashTable.prototype.del = function (key) {
            // 1.获取相应的下标值
            let index = this.hashFunc(key, this.length)
            let current = this.storage[index]
    		
    		// 2. 判断该索引位置有无数据
            // 2.1 该下标值位置没有数据,返回false,删除失败
            if(!current) {
                return false
            }
    
            // 2.2 该下标值位置有数据
            // 3. 遍历数组查找对应数据
            for (let i in current) {
            	let inner = current[i]
                // 3.1 找到对应数据了,删除该数据
                if(inner[0] === key) {
                    current.splice(i, 1)
                    this.count --
                    return inner[1]
                }
            }
    
            // 3.2 没有找到对应数据,则删除失败,返回false
            return false
        }
    }
    

    我们来使用一下该方法

    let ht = new HashTable()
    
    // 执行put()方法 6次
    ht.put('abc', '123')
    ht.put('hgf', '124')
    ht.put('wds', '125')
    ht.put('wer', '126')
    ht.put('kgl', '127')
    ht.put('kmg', '128')
    
    // 删除 key为 'hgf'的元素
    ht.del('hgf')              // 删除成功,返回 `124`
    // 删除 key为 'ppp'的元素
    ht.del('ppp')              // 删除失败,返回 false
    
    // 查看哈希表内部结构
    console.log(ht.storage)
    /* storage打印结果
    [
      [ [ 'wds', '125' ], [ 'kgl', '127' ], [ 'kmg', '128' ] ],
      [ [ 'wer', '126' ] ],
      <1 empty item>,
      [],
      [ [ 'abc', '123' ] ]
    ]
    */
    

    此时的哈希表内是这样的
    在这里插入图片描述

    (6)实现isEmpty()方法

    isEmpty()方法是用于判断哈希表是否为空。该方法无需传参

    该方法思路比较简单,直接判断属性 count 是否为 0 即可

    我们来看一下代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	//判断哈希表是否为空
        HashTable.prototype.isEmpty = function () {
        	return this.count === 0
        }
    }
    

    我们来用一下该方法

    let ht = new HashTable()
    
    console.log(ht.isEmpty())      // false,哈希表为空
    
    ht.put('abc', '123')
    
    console.log(ht.isEmpty())      // true,哈希表不为空
    

    (7)实现size()方法

    size()方法就是用于返回哈希表中数据个数。该方法也无需传参

    该方法实现思路也特别简单,直接返回属性 count 即可

    我们来看一下代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	// 返回哈希表内元素个数
        HashTable.prototype.size = function () {
            return this.count
        }
    }
    

    我们来用一下该方法

    let ht = new HashTable()
    
    console.log(ht.size())      // 0,哈希表内没有数据
    
    ht.put('abc', '123')
    
    console.log(ht.size())      // 1,哈希表内有一条数据
    

    (8)实现resize()方法

    resize()方法就是用来对哈希表的容量进行改变的,当填充因子过大,我们就对其进行扩容;当填充因子较小,我们就增加其容量。该方法接收一个参数 newLength,表示新的哈希表的容量。

    实现思路:

    1. 将原本的属性 storage 赋值给一个新的变量 oldStorage,然后我们创建一个新的空数组赋值给 storage,并将参数 newLength 赋值给属性 length
    2. 遍历 oldStorage,根据哈希表新的容量大小 newLength 将原本哈希表中所有的数据重新哈希化 、插入数据即可

    该方法难以用动图演示,所以大家好好理解一下,我们直接用代码来实现

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	//改变哈希表的容量
        HashTable.prototype.resize = function(newLength) {
            // 1.将旧的哈希表赋值给新变量
            let oldStorage = this.storage
            
            // 2.创建新的空数组作为新的哈希表容器
            this.storage = []
            
            // 3.修改哈希表容量
            this.length = newLength
    
            // 4.遍历旧的哈希表
            for(let i = 0; i < oldStorage.length; i++) {
                let box = oldStorage[i]
                // 4.1 某索引位置上没有数据
                if(box === null) {
                    continue;
                }
    
                // 4.2 某索引上有数据
                for(let j = 0; j < box.length; j++) {
                    let inner_box = box[j]
                    // 4.2.1 将数据重新经过哈希化插入到新的哈希表中
                    this.put(inner_box[0], inner_box[1])
                }
            }
        }
        
    }
    

    这里就不对该方法做过多的演示了,后面会在 put()方法 和 del() 方法的改写中用到

    (9)实现isPrime()方法

    isPrime()方法使用于判断某个数是否为质数的,因此也就只需要接收一个数字为参数即可。

    因为我们要实现哈希表的自动扩容与减容,所以在每次容量改变的时候,需要判断新的容量是否为质数,以此来保证之后哈希表中的数据均匀地分布,所以我们还是有必要来封装一下这个方法的。

    在说方法实现思路之前,我们来回顾一下,质数是只能被 1自身 整除,因此我们来看一下数字 16,显然它不是一个质数,那来看看他能被哪些数整除吧

    等于
    11616
    2816
    4416
    8216
    16116

    非常明显地看到,只要一个数能被整除,那么一个数肯定是大于等于该数的算数平方根;另一个数肯定小于等于该数的算数平方根

    因此,我们在判断一个数是否为质数时,只需从 2 开始逐个判断该数能否被整除,一直判断到该数的算数平方根即可

    那么我们来看一下代码怎么实现的吧

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	//判断是是否为质数
        HashTable.prototype.isPrime = function(number) {
            // 1.获取算数平方根,并取整
            let sqrt = Math.floor(Math.sqrt(number))
    
            // 2.从2开始遍历到算数平方根
            for(let i = 2; i <= sqrt; i++) {
                // 2.1 能被整除,返回 false
                if(number % i === 0) return false;
            }
            // 2.2 不能被整除,返回 true
            return true
        }
        
    }
    

    我们来简单验证一下该方法

    let ht = new HashTable()
    
    console.log(ht.isPrime(3));        // true
    console.log(ht.isPrime(4));        // false
    console.log(ht.isPrime(16));       // false
    console.log(ht.isPrime(11));       // true
    

    (10)实现toPrime()方法

    toPrime()方法就是用于获取离某个数最近的质数并返回,因此只需要接收一个数字作为参数即可。

    我们在实现扩容或减容时,初始会简单地 乘以2 或者 除以2,很难保证获得的数是质数,所以我们需要封装这样一个方法来将变换后的值变为质数再进行使用。

    实现思路也很简单,就一直 +1 来寻找质数就好了。

    我们来看一下代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	//获取离某个数最近地质数并返回
        HashTable.prototype.toPrime = function(number) {
    
            while(!this.isPrime(number)) {
            	number ++
            }
            return number
        } 
    }
    

    我们来简单验证一下该方法

    let ht = new HashTable()
    
    console.log(ht.toPrime(3))             // 4
    console.log(ht.toPrime(32));           // 37
    

    (11)给put()方法增加扩容功能

    什么时候需要进行给哈希表扩容呢?那肯定是在哈希表中数据量增加的时候需要考虑扩容的问题,所以我们将在 put() 方法中加上扩容的判断,上文也说到了,填充因子等于 0.75 是我们扩容的临界点,即当填充因子大于 0.75 时,就对哈希表进行扩容

    话不多说,我们直接在上文封装好的 put()方法中进行改写

    实现思路:

    1. this.count ++ 之后,判断填充因子的大小,即 this.count / this.length 是否大于 0.75,若小于 0.75,则不做任何处理
    2. 若大于 0.75,则先获取一个原来哈希表容量两倍的数 number,再调用 this.toPrime 方法获得一个离 number 最近的一个质数 prime
    3. 最后调用 this.resize 方法,并将 prime 作为参数传入,完成扩容功能

    直接来看代码吧

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	// 插入或修改数据
        HashTable.prototype.put = function (key, value) {
            // 1.哈希化获得下标值
            let index = this.hashFunc(key, this.length)
            let current = this.storage[index]
    
            // 2.判断该下标值的位置是否有数据
            // 2.1无数据
            if(!current) {
                this.storage[index] = [[key, value]]
                this.count ++
                return;
            }
            
    		// 2.2有数据
    		// 3.遍历对应索引上的数组
            for (let i = 0; i < current.length; i ++) {
                // 3.1已存在相同数据
                if(current[i][0] === key) {
                    current[i][1] = value
                    return;
                }
            }
            
            // 3.2未存在相同数据,直接添加数据
            current.push([key, value])
            this.count ++
    
    		// 4.判断是否需要进行扩容
            if(this.count / this.length >= 0.75) {
                // 4.1 将哈希表容量扩大一倍
                let newLength = this.length * 2
                // 4.2 获取质数容量
                newLength = this.toPrime(newLength)
                // 4.3 扩容
                this.resize(newLength)
            }
        }
    }
    

    (12)给del()方法增加减容功能

    同样的,在我们的 del() 方法中会涉及到数据减少的情况,即 this.count --,那么此时我们就需要考虑哈希表是否需要减少容量,也就是填充因子是否小于 0.25,若小于并且哈希表容量大于7,则进行减容;否则不做处理

    这里说一下为什么哈希表容量要大于7,因为在减容时,我们要将容量除以2,但哈希表的容量不方便太小太小,所以我就自己设定了一个容量的下限值为7,意思就是当哈希表容量小于或等于7时,即使填充因子小于0.25,也无需进行减容

    实现思路:

    1. this.count -- 之后,判断填充因子的大小,即 this.count / this.length 是小于 0.25,若大于 0.25,则不做任何处理
    2. 若小于 0.25 并且哈希表容量大于 7,则先获取一个原来哈希表容量一半的数 number,再调用 this.toPrime 方法获得一个离 number 最近的一个质数 prime
    3. 最后调用 this.resize 方法,并将 prime 作为参数传入,完成减容功能

    我们直接来看代码

    function HashTable() {
    	// 属性
    	
    	// 用于存储数据
        this.storage = []
        
        // 统计哈希表内数据个数
        this.count = 0
        
        // 设定哈希表初始长度
        this.length = 7
    
    	//封装哈希函数
        HashTable.prototype.hashFunc = function (str, size) {
            let hashCode = 0
    
            //取一个很大的数
            for (let i = 0; i < str.length; i ++) {
                hashCode = 37 * hashCode + str.charCodeAt(i)
            }
            
            //取余
            return hashCode % size
        }
    
    	// 删除数据
        HashTable.prototype.del = function (key) {
            // 1.获取相应的下标值
            let index = this.hashFunc(key, this.length)
            let current = this.storage[index]
    		
    		// 2. 判断该索引位置有无数据
            // 2.1 该下标值位置没有数据,返回false,删除失败
            if(!current) {
                return false
            }
    
            // 2.2 该下标值位置有数据
            // 3. 遍历数组查找对应数据
            for (let i in current) {
            	let inner = current[i]
                // 3.1 找到对应数据了,删除该数据
                if(inner[0] === key) {
                    current.splice(i, 1)
                    this.count --
    
    				// 判断是否需要减容
                    if(this.count / this.length < 0.25  && this.length > 7) {
                        // 将哈希表容量减小一倍
                        let number = Math.floor(this.length / 2)
                        
                        // 获取质数容量
                        number = this.toPrime(number)
                        
                        // 减容
                        this.resize(number)
                    }
    
                    return inner[1]
                }
            }
    
            // 3.2 没有找到对应数据,则删除失败,返回false
            return false
        }
    }
    

    七、结束语

    哈希表的讲解就到这里了,希望大家对哈希表有了更深一层的理解。下一篇文章我将讲解一下树结构

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • UI标签库专题:JEECG智能开发平台 BaseTag(样式和JS引入标签) 1.BaseTag(样式和JS引入标签) 1.1. 示例 1.2. 参数  属性名 类型 描述 type string JS插件类型定义如果...

        UI标签库专题一:JEECG智能开发平台 BaseTag(样式表和JS引入标签)


    1.BaseTag(样式表和JS引入标签)


    1.1. 示例

    <t:base type="jquery,easyui,tools"></t:base>

    1.2. 参数       

    属性名

    类型

    描述

    type

    string

    JS插件类型定义如果有多个以逗号隔开

          1.3.  JS插件类型

    插件名

    描述

    Jquery

    引入版本jquery-1.8.3

    Easyui

    引入版本jquery.easyui.1.3.1及自定义扩展JS

    DatePicker

    引入版本My97DatePicker4.8 Beta2

    Jqueryui

    引入版本jquery-ui-1.9.2

    prohibit

    常用浏览器操作JS函数如禁用右键菜单,禁用回退,禁用F5

    designer

    在线流程设计器函数库

    tools

    artDialog4.1.6弹出窗及常用CURD操作函数

    ckeditor

    在需要加载t:ckeditor时引入ckeditor所需要的js

    ckfinder

    在需要加载t:ckfindert:ckeditor加载ckfinder时引所需的JS

        2. Datagrid(数据表)

        2.1.DataGrid父标签

        2.1.1.示例

     <t:dategrid name="" actionUrl=""></t:dategrid>

        2.1.2. 参数

    属性名

    类型

    描述

    是否必须

    默认值

    name

    string

    表格唯一标示

    null

    treegrid

    boolean

    是否是树形列表

    false

    autoLoadData

    boolean

    数据列表是否自动加载

    true

    queryMode

    string

    查询模式:组合查询= group,单查=single

    single

    actionUrl

    string

    从远程请求数据的地址

    null

    pagination

    boolean

    是否显示分页条

    true

    title

    string

    表格标题

    null

    idField

    string

    标识字段,或者说主键字段

    null

    width

    num

    表格宽度

    auto

    height

    num

    表格高度

    auto

    checkbox

    boolean

    是否显示复选框

    false

    fit

    boolean

    是否允许表格自动缩放,以适应父容器

    true

    sortName

    string

    定义的列进行排序

    null

    sortOrder

    string

    定义列的排序顺序,只能是"递增""降序(asc,desc

    asc

    fitColumns

    boolean

    当为true时,自动展开/合同列的大小,以适应的宽度,防止横向滚动

    true

    showPageList

    boolean

    是否显示分页条数下拉框

    true

    showRefresh

    boolean

    是否显示刷新按钮

    true

    showText

    boolean

    是否显示分页文本内容

    true

    style

    string

    插件类型有easyuidatatable2

    easyui

    pageSize

    num

    每页显示的记录数

    10

        2.1.3.方法

    方法名

    传入参数

    描述

    reloadTable

    重新加载数据

    reload+name

    重新加载数据name是表格唯一标示

    get+name+Selected

    field

    获取选定行传入字段的值

    getSelected

    field

    获取选定行传入字段的值

    get+name+Selections

    field

    获取所有选定行传入字段的数组集合

    name+search

    执行查询前提是Columnquery设为true

        2.1.4.  事件

    事件名

    传出参数

    描述

    onClickRow

    rowIndex,rowData

    行单击事件

    onDblClickRow

    rowIndex,rowData

    行双击事件

    onLoadSuccess

    data

    远程数据加载成功时触发





    展开全文
  • Import Table(引入表

    千次阅读 2013-03-07 20:52:29
    首先,您得了解什么是引入函数。引入函数是被某模块调用的但又不在调用者模块中的函数,因而命名为"import(引入)"。引入函数实际位于个或者更多的DLL里。...再回顾一把,下面就是 PE header: IMAGE_NT_

    首先,您得了解什么是引入函数。一个引入函数是被某模块调用的但又不在调用者模块中的函数,因而命名为"import(引入)"。引入函数实际位于一个或者更多的DLL里。调用者模块里只保留一些函数信息,包括函数名及其驻留的DLL名。现在,我们怎样才能找到PE文件中保存的信息呢转到 data directory 寻求答案吧。再回顾一把,下面就是 PE header:

    IMAGE_NT_HEADERS STRUCT
       Signature dd ?
       FileHeader IMAGE_FILE_HEADER <>
       OptionalHeader IMAGE_OPTIONAL_HEADER <>
    IMAGE_NT_HEADERS ENDS

    optional header 最后一个成员就是 data directory(数据目录):

    IMAGE_OPTIONAL_HEADER32 STRUCT
       .... 
       LoaderFlags dd ? 
       NumberOfRvaAndSizes dd ? 
       DataDirectory IMAGE_DATA_DIRECTORY 16 dup(<>) 
    IMAGE_OPTIONAL_HEADER32 ENDS

    data directory 是一个 IMAGE_DATA_DIRECTORY 结构数组,共有16个成员。如果您还记得节表可以看作是PE文件各节的根目录的话,也可以认为 data directory 是存储在这些节里的逻辑元素的根目录。明确点,data directory 包含了PE文件中各重要数据结构的位置和尺寸信息。 每个成员包含了一个重要数据结构的信息。

    Member Info inside
    0 Export symbols
    1 Import symbols
    2 Resources
    3 Exception
    4 Security
    5 Base relocation
    6 Debug
    7 Copyright string
    8 Unknown
    9 Thread local storage (TLS)
    10 Load configuration
    11 Bound Import
    12 Import Address Table
    13 Delay Import
    14 COM descriptor

    上面那些金色显示的是我熟悉的。了解 data directory 包含域后,我们可以仔细研究它们了。data directory 的每个成员都是 IMAGE_DATA_DIRECTORY 结构类型的,其定义如下所示:

    IMAGE_DATA_DIRECTORY STRUCT 
      VirtualAddress dd ? 
      isize dd ? 
    IMAGE_DATA_DIRECTORY ENDS

    VirtualAddress 实际上是数据结构的相对虚拟地址(RVA)。比如,如果该结构是关于import symbols的,该域就包含指向IMAGE_IMPORT_DESCRIPTOR 数组的RVA。 
    isize 含有VirtualAddress所指向数据结构的字节数。

    下面就是如何找寻PE文件中重要数据结构的一般方法:

    1. 从 DOS header 定位到 PE header
    2. 从 optional header 读取 data directory 的地址。
    3. IMAGE_DATA_DIRECTORY 结构尺寸乘上找寻结构的索引号比如您要找寻import symbols的位置信息,必须用IMAGE_DATA_DIRECTORY 结构尺寸(8 bytes)乘上1import symbolsdata directory中的索引号)。
    4. 将上面的结果加上data directory地址,我们就得到包含所查询数据结构信息的 IMAGE_DATA_DIRECTORY 结构项。

    现在我们开始真正讨论引入表了。data directory数组第二项的VirtualAddress包含引入表地址。引入表实际上是一个 IMAGE_IMPORT_DESCRIPTOR 结构数组。每个结构包含PE文件引入函数的一个相关DLL的信息。比如,如果该PE文件从10个不同的DLL中引入函数,那么这个数组就有10个成员。该数组以一个全0的成员结尾。下面详细研究结构组成:

    IMAGE_IMPORT_DESCRIPTOR STRUCT 
      union 
        Characteristics dd ? 
        OriginalFirstThunk dd ? 
      ends 
      TimeDateStamp dd ? 
      ForwarderChain dd ? 
      Name1 dd ? 
      FirstThunk dd ? 
    IMAGE_IMPORT_DESCRIPTOR ENDS

    结构第一项是一个union子结构。 事实上,这个union子结构只是给 OriginalFirstThunk 增添了个别名,您也可以称其为"Characteristics"。 该成员项含有指向一个IMAGE_THUNK_DATA 结构数组的RVA
    什么是 
    IMAGE_THUNK_DATA这是一个dword类型的集合。通常我们将其解释为指向一个 IMAGE_IMPORT_BY_NAME 结构的指针。注意 IMAGE_THUNK_DATA 包含了指向一个IMAGE_IMPORT_BY_NAME 结构的指针而不是结构本身。
    请看这里
    现有几个 IMAGE_IMPORT_BY_NAME 结构,我们收集起这些结构的RVA (IMAGE_THUNK_DATAs)组成一个数组,并以0结尾,然后再将数组的RVA放入 OriginalFirstThunk
    此 
    IMAGE_IMPORT_BY_NAME 结构存有一个引入函数的相关信息。再来研究 IMAGE_IMPORT_BY_NAME 结构到底是什么样子的呢:

    IMAGE_IMPORT_BY_NAME STRUCT 
      Hint dw ? 
      Name1 db ? 
    IMAGE_IMPORT_BY_NAME ENDS

    Hint 指示本函数在其所驻留DLL的引出表中的索引号。该域被PE装载器用来在DLL的引出表里快速查询函数。该值不是必须的,一些连接器将此值设为0
    Name1 含有引入函数的函数名。函数名是一个ASCIIZ字符串。注意这里虽然将Name1的大小定义成字节,其实它是可变尺寸域,只不过我们没有更好方法来表示结构中的可变尺寸域。The structure is provided so that you can refer to the data structure with descriptive names.

    TimeDateStamp 和 ForwarderChain 可是高级东东让我们精通其他成员后再来讨论它们吧。

    Name1 含有指向DLL名字的RVA,即指向DLL名字的指针,也是一个ASCIIZ字符串。

    FirstThunk 与 OriginalFirstThunk 非常相似,它也包含指向一个 IMAGE_THUNK_DATA 结构数组的RVA(当然这是另外一个IMAGE_THUNK_DATA 结构数组)。 
    好了,如果您还在犯糊涂,就朝这边看过来
    现在有几个 IMAGE_IMPORT_BY_NAME 结构,同时您又创建了两个结构数组,并同样寸入指向那些 IMAGE_IMPORT_BY_NAME 结构的RVAs,这样两个数组就包含相同数值了(可谓相当精确的复制啊)。 最后您决定将第一个数组的RVA赋给 OriginalFirstThunk第二个数组的RVA赋给 FirstThunk,这样一切都很清楚了。

    OriginalFirstThunk   IMAGE_IMPORT_BY_NAME   FirstThunk

    |

          |
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    ...
    IMAGE_THUNK_DATA
    --->
    --->
    --->
    --->
    --->
    --->
    Function 1
    Function 2
    Function 3
    Function 4
    ...
    Function n
    <---
    <---
    <---
    <---
    <---
    <---
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    ...
    IMAGE_THUNK_DATA

    现在您应该明白我的意思。不要被IMAGE_THUNK_DATA这个名字弄糊涂它仅是指向 IMAGE_IMPORT_BY_NAME 结构的RVA。 如果将 IMAGE_THUNK_DATA 字眼想象成RVA,就更容易明白了。OriginalFirstThunk 和 FirstThunk 所指向的这两个数组大小取决于PE文件从DLL中引入函数的数目。比如,如果PE文件从kernel32.dll中引入10个函数,那么IMAGE_IMPORT_DESCRIPTOR 结构的 Name1域包含指向字符串"kernel32.dll"RVA,同时每个IMAGE_THUNK_DATA 数组有10个元素。

    下一个问题是为什么我们需要两个完全相同的数组为了回答该问题,我们需要了解当PE文件被装载到内存时,PE装载器将查找IMAGE_THUNK_DATA 和 IMAGE_IMPORT_BY_NAME 这些结构数组,以此决定引入函数的地址。然后用引入函数真实地址来替代由FirstThunk指向的 IMAGE_THUNK_DATA 数组里的元素值。因此当PE文件准备执行时,上图已转换成:

    OriginalFirstThunk   IMAGE_IMPORT_BY_NAME   FirstThunk

    |

          |
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    IMAGE_THUNK_DATA
    ...
    IMAGE_THUNK_DATA
    --->
    --->
    --->
    --->
    --->
    --->
    Function 1
    Function 2
    Function 3
    Function 4
    ...
    Function n
     
     
     
     
     
    Address of Function 1
    Address of Function 2
    Address of Function 3
    Address of Function 4
    ...
    Address of Function n

    OriginalFirstThunk 指向的RVA数组始终不会改变,所以若还反过头来查找引入函数名,PE装载器还能找寻到。
    当然再简单的事物都有其复杂的一面。有些情况下一些函数仅由序数引出,也就是说您不能用函数名来调用它们您只能用它们的位置来调用。此时,调用者模块中就不存在该函数的IMAGE_IMPORT_BY_NAME 结构。不同的,对应该函数的 IMAGE_THUNK_DATA 值的低位字指示函数序数,而最高二进位 (MSB)设为1。例如,如果一个函数只由序数引出且其序数是1234h,那么对应该函数的 IMAGE_THUNK_DATA 值是80001234hMicrosoft提供了一个方便的常量来测试dword值的MSB位,就是 IMAGE_ORDINAL_FLAG32,其值为80000000h
    假设我们要列出某个
    PE文件的所有引入函数,可以照着下面步骤走:

    1. 校验文件是否是有效的PE
    2. 从 DOS header 定位到 PE header
    3. 获取位于 OptionalHeader 数据目录地址。
    4. 转至数据目录的第二个成员提取其VirtualAddress值。
    5. 利用上值定位第一个 IMAGE_IMPORT_DESCRIPTOR 结构。
    6. 检查 OriginalFirstThunk值。若不为0,顺着 OriginalFirstThunk 里的RVA值转入那个RVA数组。若 OriginalFirstThunk 0,就改用FirstThunk值。有些连接器生成PE文件时会置OriginalFirstThunk值为0,这应该算是个bug。不过为了安全起见,我们还是检查 OriginalFirstThunk值先。
    7. 对于每个数组元素,我们比对元素值是否等于IMAGE_ORDINAL_FLAG32如果该元素值的最高二进位为1, 那么函数是由序数引入的,可以从该值的低字节提取序数。
    8. 如果元素值的最高二进位为0,就可将该值作为RVA转入 IMAGE_IMPORT_BY_NAME 数组,跳过 Hint 就是函数名字了。
    9. 再跳至下一个数组元素提取函数名一直到数组底部(它以null结尾)。现在我们已遍历完一个DLL的引入函数,接下去处理下一个DLL
    10. 即跳转到下一个 IMAGE_IMPORT_DESCRIPTOR 并处理之,如此这般循环直到数组见底。(IMAGE_IMPORT_DESCRIPTOR 数组以一个全0域元素结尾)


    typedef struct _IMAGE_THUNK_DATA32 {
    union {
    PBYTE ForwarderString;
    PDWORD Function;
    DWORD Ordinal;
    PIMAGE_IMPORT_BY_NAME AddressOfData;
    } u1;
    } IMAGE_THUNK_DATA32;

    对于IMAGE_THUNK_DATA,如果最高位为1,则表示函数以序号的方式从DLL中导出引用,低31位表示序号;如果最高位为0,则表示名字导出,此时32位表示一个RVA,这个RVA指向一个结构为IMAGE_IMPORT_BY_NAME的元素。

    从上图我们可以看出有两个并行的指针数组都指向IMAGE_IMPORT_BY_NAME结构.事实上,OriginalFirstThunk指向的IMAGE_THUNK_DATA结构数组从来不被修改,该数组有时也叫提示名表(Hint-name table),提示名表总是指向IMAGE_IMPORT_BY_NAME结构数组.而FirstThunk指向的IMAGE_THUNK_DATA结构数组在该pe文件被加载时,加载程序会修改该数组的内容.加载程序迭代搜索数组的每一个指针,找到每一个IMAGE_IMPORT_BY_NAME结构所对应的输入函数的地址,然后加载程序用找到的地址修改相应的IMAGE_THUNK_DATA结构.

    展开全文
  • 数据结构 图的邻接

    万次阅读 多人点赞 2018-05-08 20:46:32
    邻接的出现是因为图若是稀疏图,用邻接矩阵会造成空间的浪费,毕竟你要开辟维数组和维数组嘛,而且还是大开小用的那种。 邻接为了避免内存的浪费引入了链式存储,它的处理办法是: 1.用维...

    呃,下面该写邻接表了.......

    邻接表的出现是因为图若是稀疏图,用邻接矩阵会造成空间的浪费,毕竟你要开辟一个一维数组和一个二维数组嘛,而且还是大开小用的那种。

    邻接表为了避免内存的浪费引入了链式存储,它的处理办法是:

    1.用一个一维数组存储顶点,当然你也可以用单链表存储,

    2.用单链表存储顶点的邻接点,可以将顶点改为结构体数组,结构体中存放邻接点的指针,邻接点也创建一个结构体,定义指针next存放该顶点的另一个邻接点,这样就可以把该顶点的所有邻接点串起来了。

    下面是一个无向的网图:

    邻接表中数据的存储图示如下(emmm,无向图果然没有有向图好画):

    emmm,终于画完了,我来介绍下这个图

    顶点表也就是个结构体数组,是存放顶点的结构,顶点表中有data元素,存放顶点信息  firstarc是一个边结构体表指针,存放邻接点的信息。

    边表也是一个结构体,内有adivex元素,存放邻接点的下标,weight存放顶点与邻接点之间线的权重,next是边表结构体指针,存放该顶点的下一个邻接点,next就是负责将顶点的邻接点连起来。

    看着上面的图慢慢理解吧!

    下面则是代码部分:

    #include <iostream>
    using namespace std;
    
    #define MAXVERTEX 100   //最大顶点数
    typedef char vertextype;    //定义顶点的存储类型
    typedef int arctype;    //定义边的权值类型
    
    typedef struct ArcNode  //边表节点
    {
        int adjvex; //邻接点域,存储该顶点对应的下标
        arctype wigth;  //用于存储权值
        struct ArcNode *next; //链域,指向下一个邻接点
    }ArcNode;
    
    typedef struct VertexNode   //顶点表节点
    {
        vertextype data;    //存储顶点数据的信息
        ArcNode *firstarc;  //边表头指针
    }VertexNode, AdjList[MAXVERTEX];
    
    typedef struct
    {
        AdjList adjlist;    //定义邻接表
        int numvertex;  //当前邻接表的顶点数
        int numarc; //当前邻接表的边数
    }GraphAdjList;
    
    //建立图的邻接表
    void CreateAdjListGraph(GraphAdjList &G)
    {
        ArcNode *e;
        cin >> G.numvertex; //输入当前图的顶点数
        cin >> G.numarc;    //输入当前图的边数
        for(int i = 0; i < G.numvertex; i++)    //建立顶点表
        {
            cin >> G.adjlist[i].data;   //输入顶点信息
            G.adjlist[i].firstarc = NULL;   //将表边指针置为空
        }
        for(int k = 0; k < G.numarc; k++)
        {
            int i, j, w;
            cin >> i >> j >> w; //输入边两边的顶点和边上的权重
            e = new ArcNode;   //创建一个表边节点指针
            e->adjvex = j;
            e->wigth = w;
            e->next = G.adjlist[i].firstarc;
            G.adjlist[i].firstarc = e;
            //因为是无向图,彼此相对称
            e = new ArcNode;   //创建一个表边节点指针
            e->adjvex = i;
            e->wigth = w;
            e->next = G.adjlist[j].firstarc;
            G.adjlist[j].firstarc = e;
        }
    }
    
    //打印邻接表
    void PrintfGraphAdjList(GraphAdjList G)
    {
        for(int i = 0; i < G.numvertex; i++)
        {
            ArcNode *p = G.adjlist[i].firstarc;
            cout << G.adjlist[i].data << '\t';
            while(p)
            {
                cout << p->adjvex << ' ' << p->wigth << '\t';
                p = p->next;
            }
            cout << endl;
        }
    }
    int main()
    {
        GraphAdjList G;
        CreateAdjListGraph(G);
        PrintfGraphAdjList(G);
        return 0;
    }
    


    邻接表的时间复杂度:n为顶点数,e为边数 O(n + e)……

     

    运行结果(根据上图的信息输入):

     

     

    展开全文
  • 先寻找值大于等于k1的第个元素(第个删除的数据元素),然后寻找值大于k2的第数据元素(最后个删除的下个元素),将后面所有结点前移即可。 核心算法: #define MaxSize 50 //长度的初始定义 typedef ...
  • 在react中我们可以实现数据的绑定。可以绑定组件的属性数据、...、绑定数据 1 绑定数据  绑定的数据我们一般要放在构造函数中,如下:  通过this.state定义我们要绑定的数据,然后在组件的属性值位置我们可...
  • 最初就是直接新建flutter项目,就会自动建立个入门项目。(开始项目前,需先学习Dart语言) flutter项目代码都在lib目录下编写: 新建包,新建dart类,在dart类中编写 flutter 插件引入: (可以看项目中如何引入...
  • 前言最近在写项目的时候遇到个问题,在使用easyui编写前台页面有时候在新添加数据或者修改数据的时候要求不能以弹框的形式实现,需要直接在原来表格的下面直接增加行,并且可以直接点击某单元格进行编辑或...
  • 数据结构之广义

    千次阅读 2018-05-25 23:47:59
    如果允许中的元素具有某种结构,这就引入了广义的概念。广义的定义如下: 语法图如下: 举个例子: 2.数据结构 结构: 为什么需要头节点?便于在表头增加删除结点。如果不要头结点,那么对广义的表头...
  • 1. 结构完全一样 insert into 1 select * from 表2 2.... select 列1,列2,列3 from 23、只从另外取部分值insert into 1 (列名1,列名2,列名3) values(列1,列2,(select 列3 from 表2));转...
  • 效果如下: 实验如下: 在Excel中选中某个单元格后,选择工具栏中的数据->数据验证->数据验证 在来源中选择你想要选择的sheet的分布。 ...
  • 数据仓库--事实和维度

    千次阅读 2018-07-31 23:06:08
    1.数据仓库与操作型数据库的区别 数据仓库的物理模型与常见的操作型数据库的物理模型有很大不同。最明显的区别是:操作型数据库主要是用来支撑即时操作,对数据库的性能和质量要求都比较高,为了防止“garbage in...
  • 王佩丰数据透视到五讲)

    千次阅读 2018-06-24 15:03:33
    创建数据透视选中数据区域,然后插入数据透视即可。自定义字段到透视中,双击值字段中的数据,可以跳转到该数据数据源。避免源数据泄漏:复制粘贴时仅粘贴表格中的数据。如果删除掉字段中的某个项目,下拉框...
  •  1.模块的使用和引用 在apicloud的模块store里面提供了大量的模块,我们可以直接在html里面引入使用 使用方法:在需要使用模块的页面中加入: ...2.服务器数据对接---云数据库和本地服务器 1.、
  •  C语言 今天学习了思成老师的数据结构实战教程 写了个顺序 插入和删除的操作 源码共享给大家 一共包括list.c stu.h main.c list.h .h文件是头文件 需要引入 具体的功能我都已经在代码中写明了 list.h代码...
  • MySql存储过程动态创建并插入数据

    万次阅读 热门讨论 2015-07-31 20:45:54
    数据库用的是MySql,对于MySql不是很熟练,只是会简单的应用,毕竟简单的sql语句还是相通的,但是随着项目的深入复杂的sql语句开始慢慢多起来,其中个小难点就是要根据当天的日期动态创建,并且向其中插入数据。...
  • 一般来讲,任何 MySql 数据类型都可以被转换为个 java.lang.String,任何 MySql 数字类型都可以被转换为任何种 Java 数字类型(当然这样也可能出一些四舍五入,溢出,精度丢失之类的问题)。转换MySql 数据类型...
  • 存储过程中merge into 一般用于增量插入数据,如果是源全量数据插入目标常规认为insert into 比merge into 效率更高, 但是数据数据来源是需要查询大量关联时然后全量录入目标时,merge into 后面的...
  • 三种妙法搞定冗余表数据一致性

    千次阅读 2016-05-30 22:36:52
    互联网很多业务场景的数据量很大,此时数据库架构要进行水平切分,水平切分会有个patition key,通过patition key的查询能够直接定位到库,但是非patition key上的查询可能就需要扫描多个库了。
  • Vue 在项目中引入本地Json数据

    万次阅读 2018-07-16 11:19:07
    在build文件夹中,找到 webpack.dev.conf.js ,我们需要在这个js文件中配置Json在它后面加上配置数据就OK //第步 const portfinder = require('portfinder'),在后面加上 const express = require('express'); ...
  • 有两个分别是 A用户下的 T_SRC_WEATHER_TSPG字段如图,B用户下的t_src_weather ,如图:要求,当A用户下的T_SRC_WEATHER_TSPG有插入或者更新数据时,同时将数据同步至B用户下的t_src_weather中,创建触发器,...
  • 同步两个数据库之间两数据也许的数据库管理员偶尔需要做的件事情,下面来记录一下常用的两种方法: 方法:使用delete、truncate 方法:使用 merge into ,Merge是在SQL Server 2008被引入,它能将...
  • 使用SpringBoot的主要思想是习惯大于配置。使用Java配置代替XML配置。 在实际应用开发过程中也会存在不得不添加配置文件的情况...模拟创建个不和启动类在同个包中的bean,编写spring配置文件由容器负责实例化。...
  • Excel数据导入sql临时操作步骤

    千次阅读 2019-04-26 09:39:17
    主要介绍2种操作方法:拼接法和SSMS引入、拼接法: 打开ssms,先创建一张临时,语句如下: --创建临时 CREATE table #temp (fname varchar(100),fnumber varchar(100)) 打开需要导入的Excel,...
  • 我们有时候会一些公共方法写到个单独的js文件,这样方便多处使用该方法,也很方便找到或者修改方法。 例:我们在写项目的时候会遇到加载本地城市列表的数据,如果放到vue组件里,是极其的不方便,我们来看看怎么...
  • 使用SQL语句修改表数据

    千次阅读 2021-10-05 15:12:55
    使用SQL语句修改表数据 利用INSERT语句输入数据 INSERT语句的基本语法格式如下: 上述格式主要参数说明如下: TOP(expression)[PERCENT]:指定将插入的随机行的数目或百分比。 INTO:个可选的关键字,可以将它...
  • 设计数据表,遇到个很常见的情况。、中间-多对多关系的转化实际中,经常存在多对多关系。以订单和商品为例,个订单对应多个商品,个商品也对应多个订单。此时在将E-R图转化为关系模型时,需要引入中间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,332,702
精华内容 533,080
关键字:

怎么把表一的数据引入表二