大家好，我是晓彬，今天我们讨论ORACLE数据库中的HASH链表。
一、HASH算法
在讨论链表之前我们先分享HASH算法。Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
哈希表是根据设定的哈希函数H（key）和处理冲突方法将一组关键字映射到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。
通过将单向数学函数（有时称为“哈希算法”）应用到任意数量的数据所得到的固定大小的结果。如果输入数据中有变化，则哈希也会发生变化。哈希可用于许多操作，包括身份验证和数字签名。也称为“消息摘要”。
哈希（Hash）算法，即散列函数。它是一种单向密码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。
散列表，它是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法。顾名思义，该数据结构可以理解为一个线性表，但是其中的元素不是紧密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是根据关键码值（Key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
二、HASH链表
HASH链表是由HASH表和CBC链表组合成，简称HASH链表。HASH算法中HASH表由HASH BUCKET构成，HASH BUCKET的数据量由db_block_hash_buckets参数设置。
HASH表示意图：
ORACLE中逻辑读主要就是利用的HASH链表。
逻辑读的主要流程如下：
1、进程根据要访问的块的文件号、块号通过HASH函数计算HASH值。
2、通过HASH值找到HASH BUCKET。
3、搜索BUCHET后面的CBC链表。找到目标BH
4、通过目标BH找到BA
5、通过BA方位BUFFER
如果没有找到包含目标文件号、和块号的BH那么久需要物理读。
读取数据详细步骤：
第一步、在获得CBC链表时需要获得CBC LATCH，大多以共享方式获得
第二步、在CBC LATCH保护下查找目标BH中的BA
第三步、在CBC LATCH保护下获得BA地址，进一步查到BUFFER中的数据
第四步、查询完成后释放CBC LATCH
三、HASH链表中的CBC LATCH争用
由于一个CBC LATCH可以保护多个链表、以及一个链表可能有多个BH所以当发生以下情况时会出现CBC LATCH争用。
1、多个进程频繁的以不兼容模式访问申请获得同一个CBC LATCH访问该CBC LATCH下面的不同链表和不同BH(热链竞争)
(1)解决方法：修改DB_BLOCK_HASH_BUCKETS和DB_BLOCK_HASH_latches
(2)热链竞争应用举例：
A、找出表的文件号和块号
SELECT DBMS_ROWID.ROWID_RELATIVE_FNO(ROWID) FILE_ID,
DBMS_ROWID.ROWID_BLOCK_NUMBER(ROWID) BLOCK_ID
FROM LIUXIAOBIN;
B、根据文件号、块号获得CBC LATCH 地址
SELECT HLADDR FROM X$BH WHERE FILE#=11 AND DBABLK=180;
C、根据LATCH地址找到CBC LATCH保护的哪些BUFFER
SELECT FILE#, DBABLK, OWNER, OBJECT_NAME
FROM X$BH A, DBA_OBJECTS B
WHERE HLADDR = '00007FFEF52F9BA8'
AND A.OBJ = B.DATA_OBJECT_ID;
SELECT dbms_rowid.rowid_create(1,267,11,180,1) FROM dual;
注释：以上没有找到同一个LATCH的不同链表
2、多个进程频繁的以不兼容模式访问申请获得同一个CBC LATCH访问该CBC LATCH下面的同一链表下的同一BH（热块竞争）
在两个会话执行以下语句：
declare
n VARCHAR2(40);
begin
for i in 1..10000000 loop
SELECT NAME into n from liuxiaobin WHERE ID = 1;
end loop;
end;
在第三个会话执行以下语句：
SELECT SID,EVENT,P1RAW,P2RAW FROM V$SESSION WHERE WAIT_CLASS<>'Idle' ORDER BY event
注释：这列子成了MUTEX竞争。
四、BUFFER BUSY WAITS
Oracle读不会阻塞写，但是写会阻塞读。
举例：A、B、C三个进程。
第一步：A进程在获得CBC LATCH后 将BH中的BUFFER PIN锁修改为共享模式S
第二步：B进程向修改BUFFER，他先获得CBC LATCH共享模式
第三步：B进程获得BH后发现BH被其他进程修改为共享模式了，然后B进程要修改数据，所以他必须是独占模式，所以他讲BUSSER和BH都复制一份
第四步：复制后讲复制前的BH 加一个状态STATUS 为：CR(一直读链表) 复制后的BH STATUS 为：XCUR（当前最新链表）并且在新BH中BUFFER PIN锁为独占锁。
第五步：修改BUFFER
第六步：当B进程还未完成修这时候C进程要读当前B进程要修改的BUFFER这个时候就回产生BUFFER BUSY WAIT，这种情况一般是DML操作产生。