Oracle Hash

一，简单演示hash算法
二、详解oracle中是如何使用hash算法的
三、名词解释：
四、生动的例子：什么叫哈希表(Hash Table)

一，简单演示hash算法
　　在介绍library cache的内部管理机制前，先简单介绍一下所谓的hash算法。
　　oracle内部在实现管理的过程中大量用到了hash算法。hash算法是为了能够进行快速查找定位所使用一种技术。哈希表是一个以空间换取时间的数据结构 。所谓hash算法，就是根据要查找的值，对该值进行一定的hash算法后得出该值所在的索引号，然后进入到该值应该存在的一列数值列表（可以理解为一个二维数组）里，通过该索引号去找它应该属于哪一个列表。然后再进入所确定的列表里，对其中所含有的值，进行一个一个的比较，从而找到该值。这样就避免了对整个数值列表进行扫描才能找到该值，这种全扫描的方式显然要比hash查找方式低效很多。其中，每个索引号对应的数值列在oracle里都叫做一个hash bucket.

我们来列举一个最简单的hash算法。假设我们的数值列表最多可以有10个元素，也就是有10个hash buckets，每个元素最多可以包含20个数值。则对应的二维数组就是t[10][20].我们可以定义hash算法为n MOD 10.通过这种算法，可以将所有进入的数据均匀放在10个hash bucket里面，hash bucket编号从0到9.比如，我们把1到100都通过这个hash函数均匀放到这10个hash bucket里，当查找32在哪里时，只要将32 MOD 10等于2，这样就知道可以到2号hash bucket里去找，也就是到t[2][20]里去找，2号hash bucket里有10个数值，逐个比较2号hash bucket里是否存在32就可以了。
【oracle】hash - bkeep - zhengbin

二、详解oracle中是如何使用hash算法的
library cache就是使用多个hash bucket来管理的，其hash算法当然比我们前面列举的要复杂多了。每个hash bucket后面都串连着多个句柄（该句柄叫做library cache object handle），这些句柄描述了library cache里的对象的一些属性，包括名称、标记、指向对象所处的内存地址的指针等。可以用下图一来描述library cache的整体结构。
Tips：我的理解：hash bucket后面跟了句柄（handle）—->句柄里面包括了各种内存管理信息—->Heap0（内存指针，堆）是对象的概要信息，下面又有heap1…heap6…记录了详细信息。
【oracle】hash - bkeep - zhengbin

【我的理解】SQL语句进入library cache ：SQL文本转换为ASCII====>hash ASCII (sql语句文本+命名空间)====>得到一个hash值，即就是hash bucket号====>SQL语句被分配到该号的hash bucket里面去

Tips：Oracle根据 shared_pool_size所指定的shared pool尺寸自动计算hash buckets的个数，shared pool越大，则可以挂载的对象句柄就越多。

当一条SQL语句进入library cache的时候，先将SQL文本转化为对应ASCII数值，然后对该这些ASCII数值进行hash函数的运算，传入函数的是SQL语句的名称（name，对于SQL语句来说其name就是SQL语句的文本）以及命名空间（namespace，对于SQL语句来说是“SQL AREA”，表示共享游标。可以从视图v$librarycache里找到所有的namespace）。运用hash函数后得到一个值，该值就是hash buckets的号码，从而该SQL语句被分配到该号的hash bucket里去。实际上，hash bucket就是通过串连起来的对象句柄才体现出来的，它本身是一个逻辑上的概念，是一个逻辑组，而不像对象是一个具体的实体。Oracle根据 shared_pool_size所指定的shared pool尺寸自动计算hash buckets的个数，shared pool越大，则可以挂载的对象句柄就越多。

【重要原理】SQL语句进入library cache的时候，具体处理过程。
【理解】SQL语句的文本都通过句柄来访问。可以把library cache理解为一本书，而SQL语句的对象就是书中的页，而句柄就是目录，通过目录可以快速定位到指定内容的页。

当某个进程需要处理某个对象时，比如处理一条新进入的SQL语句时，它会对该SQL语句应用hash函数算法，以决定其所在的hash bucket的编号，然后进入该hash bucket进行扫描并比较。有可能会发生该对象的句柄存在，但是句柄所指向的对象已经被交换出内存的情况出现。这时对应的对象必须被再次装载（reload）。也可能该对象的句柄都不存在，这时进程必须重新构建一个对象句柄挂到hash bucket上，然后再重新装载对象。SQL语句相关的对象有很多（最直观的就是SQL语句的文本），这些对象都存放在library cache里，SQL语句的文本都通过句柄来访问。可以把library cache理解为一本书，而SQL语句的对象就是书中的页，而句柄就是目录，通过目录可以快速定位到指定内容的页。

对象句柄（objects handle）存放了那些信息呢？
对象句柄存放了对象的名称（name）、对象所属的命名空间（namespace）、有关对象的一些标记（比如对象是否为只读、为本地对象还是远程对象、是否被pin在内存中等等）以及有关对象的一些统计信息等。而且，对象句柄中还存放了当前正在lock住和pin住该对象的用户列表、以及当前正在等待 lock和pin该对象的用户列表。对象句柄中存放的最重要的内容就是指向Heap 0对象的指针了。Heap 0用来存放与对象有直接关系的一些信息，比如对象类型、对象相关的表（比如依赖表、子表等）、指向对象的其他数据块的指针（这些数据块指向了实际存放 SQL文本、PL/SQL代码、错误信息等的大内存块，这些大内存块依次叫做Heap 1、2、3、4等）等信息。
三、名词解释：
u Library cache: SGA—>Shared Pool —>Library Cache
u hash算法:是为了能够进行快速查找定位所使用一种技术。哈希表是一个以空间换取时间的数据结构
u hash bucket: library cache就是使用多个hash bucket来管理的
u handle:句柄；句柄描述了library cache里的对象的一些属性，包括名称、标记、指向对象所处的内存地址的指针等
u SQL语句的名称：name，对于SQL语句来说其name就是SQL语句的文本
u 命名空间：namespace，对于SQL语句来说是“SQL AREA”，表示共享游标。
u pin：定在内存里面
u Heap：内存指针
u Heap 0：用来存放与对象有直接关系的一些信息，比如对象类型、对象相关的表（比如依赖表、子表等）、指向对象的其他数据块的指针（Heap1…Heap6）
u Heap1…Heap6: 实际存放 SQL文本、PL/SQL代码、错误信息等的大内存块。
u 把library cache理解为一本书，而SQL语句的对象就是书中的页，而句柄（handle）就是目录，通过目录可以快速定位到指定内容的页。

四、生动的例子：什么叫哈希表(Hash Table) 散列表（也叫哈希表），是根据关键码值直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 数据结构中，有个时间算法复杂度O(n)的概念来衡量某种算法在时间效率上的优劣。哈希表的理想算法复杂度为O(1)，也就是说利用哈希表查找某个值，系统所使用的时间在理想情况下为定值，这就是它的优势。那么哈希表是如何做到这一点的呢？ 我们定义一个很大的有序数组，想要得到位于该数组第n个位置的值，它的算法复杂度为O(1)。哈希表利用哈希函数将需要存储的内容的关键值转换为这个有序 数组中的某个值，在被存储内容和有序数组之间建立了映射关系。这样，下次我们对这个值进行查找时只要使用同一个哈希函数对关键值进行转换，找到这个数组值 就可以了。 我们来举个例子。假设我们要做个存储结构，需要存储下来寰联的人物，以及他们的详细信息。我们用他们的名字来作为存储 的关键值，例如：刘凡，傅勇，沈卫国，郑彬，张宝东……等等。这个时候我们如果想用一般的方法来查找这些英雄豪杰，需要遍历整个存储空间，如果这些英雄豪杰一 共有n个，那么这时候的时间算法复杂度为O(n)。显然如果n值很大，每次想要找到某个英雄就需要比较长的时间。 此时我们先定义一个大的有序结构数组HashValue[m]，用来存放各位英雄豪杰的信息。然后编写一个哈希函数ChangeToHashValue (name)，函数的具体内容就不细说了，反正这个函数会将这些做为关键值的名字转换为HashValue[m]中的某个下标值x。然后可以将英雄的信息 放进HashValue[x]中去。这样，可以将所有英雄的信息存储起来。当查询的时候再使用哈希函数ChangeToHashValue(name)得 到这个下标值，这样就很容易得到了这个英雄的信息。例如：ChangeToHashValue(刘凡)为10，那么就将刘备存储到HashValue [10]里面。当查询的时候再次使用ChangeToHashValue(刘凡)得到10，这个时候我们就可以很容易找到刘凡的所有信息。在实际应用中如 果我们想把所有的英雄豪杰都存储进系统时，需要定义m>n。就是数组的大小要大于需要存储的信息量，所以说哈希表是一个以空间换取时间的数据结构。 这个时候问题来了，出现了这种情况ChangeToHashValue(郑彬)和ChangeToHashValue(沈卫国)得到的值是一样的，都是 250，我们岂不是在存储过程中会遇到麻烦，怎么安排他们二位的地方呢（总不能让二位打一架，谁赢了谁呆在那吧），这就需要一个解决冲突的方法。当遇到这 种情况时我们可以这样处理，先存储好了郑彬，当沈卫国进入系统时会发现郑彬已经是250了，那咱就加一位，251得了，这不就解决了。我们查找沈卫国的时候也是，一看250不是沈卫国，那就加个1，就找到了。这时还存在一个问题。直接用ChangeToHashValue(张宝东)为251，沈卫国已经早早占了他的 地方，那就再加1存到252呗。呵呵，这时我们会发现，当哈希函数冲突发生的机率很高时，可能会有一群英雄豪杰在250这个值后面扎堆排队。要命的是查找 的时候，时间算法复杂度早已不是O(1)了（所以我们说理想情况下哈希表的时间算法复杂度为O(1)）。 这就是说哈希函数的编写是哈希表的一个关键问题，会涉及到一个存储值在哈希表中的统计分布。如果哈希函数已经定义好了，冲突的解决就成为了改变系统性能的 关键因素。其实还有很多种方法来解决冲突情况下的存储和查找问题，不一定非要线性向后排队，如果有好的哈希表冲突的解决方法也能很大程度上提高系统的效率。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!