size_t
key_offset,key_length;
/* Length of key if const length */
size_t
blength;
ulong records;
uint flags;
DYNAMIC_ARRAY array;
/* Place for hash_keys */
my_hash_get_key get_key;
void
free
void
CHARSET_INFO *charset;
} HASH;
blength

 records

 flags

 array

 get_key

 free

 charset

 > </font><font size=
"3"

_my_hash_init(A,0,B,C,D,E,F,G,H)
#define my_hash_init2(A,B,C,D,E,F,G,H,I) \
_my_hash_init(A,B,C,D,E,F,G,H,I)
@brief Initialize the hash
@details
Initialize the hash, by defining and giving valid values for
its elements. The failure to allocate memory for the
hash->array element will not result in a fatal failure. The
dynamic array that is part of the hash will allocate memory
as required during insertion.
@param[in,out] hash         The hash that is initialized
@param[in]     charset      The charater set information
@param[in]     size         The hash size
@param[in]     key_offest   The key offset for the hash
@param[in]     key_length   The length of the key used in
the hash
@param[in]     get_key      get the key for the hash
@param[in]     free_element pointer to the function that
does cleanup
@return        inidicates success or failure of initialization
@retval 0 success
@retval 1 failure
my_bool
_my_hash_init(HASH *hash, uint growth_size, CHARSET_INFO *charset,
ulong size,
size_t
key_offset,
size_t
key_length,
my_hash_get_key get_key,
void
(*free_element)(
void
*), uint flags)
DBUG_ENTER(
"my_hash_init"
DBUG_PRINT(
"enter"
"hash: 0x%lx  size: %u"
long
) hash, (uint) size));
hash->records=0;
hash->key_offset=key_offset;
hash->key_length=key_length;
hash->blength=1;
hash->get_key=get_key;
hash->
free
=free_element;
hash->flags=flags;
hash->charset=charset;
DBUG_RETURN(my_init_dynamic_array_ci(&hash->array,
sizeof
(HASH_LINK), size, growth_size));
<font size=
"3"
>   可以看到，_my_hash_init函数主要是初始化HASH结构体和hash->array（DYNAMIC_ARRAY结构体）。</font>
<font size=
"3"
>   我们首先来看下hash函数的定义：</font>
my_bool first)
(hash->get_key)
return
char
*) (*hash->get_key)(record,length,first);
*length=hash->key_length;
return
char
*) record+hash->key_offset;
static
uint my_hash_mask(my_hash_value_type hashnr,
size_t
buffmax,
size_t
maxlength)
((hashnr & (buffmax-1)) < maxlength)
return
(hashnr & (buffmax-1));
return
(hashnr & ((buffmax >> 1) -1));

"Yan"
== Yan Yu <yan2...@facebook.com> writes:
Yan> Dear MySQL experts:
Yan>      Thank you so much
for
your reply to my previous Qs, they are very
Yan> helpful!
Yan>      Could someone please help me understand function my_hash_insert()
Yan> in mysys/hash.cc?
Yan> what are lines 352 -429 trying to achieve?  Are they just some
Yan> optimization to shuffle existing
Yan> hash entries in the table (since the existing hash entries may be in
Yan> the wrong slot due to chaining
Yan> in the
case
of hash collision)?
<strong><font color=
"#ff0000"
>The hash algorithm is based on dynamic hashing without empty slots.</font></strong>
This means that when you insert a
new
key, in some cases a small set
of old keys needs to be moved to other buckets.  This is what the code
does.
Regards,
Monty

<a href=
"http://images.cnblogs.com/cnblogs_com/nocode/201110/201110142107072298.png"
><img title=
"image"
style=
"border-width: 0px; display: block; float: none; margin-left: auto; margin-right: auto;"
alt=
"image"
src=
"http://images.cnblogs.com/cnblogs_com/nocode/201110/201110142107114127.png"
border=
"0"
height=
"910"
width=
"570"
><
>

uchar *UNINIT_VAR(ptr_to_rec),*UNINIT_VAR(ptr_to_rec2);
HASH_LINK *data,*empty,*UNINIT_VAR(gpos),*UNINIT_VAR(gpos2),*pos;
(HASH_UNIQUE & info->flags)
uchar *key= (uchar*) my_hash_key(info, record, &idx, 1);
(my_hash_search(info, key, idx))
return
(TRUE);
/* Duplicate entry */
flag=0;
(!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
return
(TRUE);
/* No more memory */
data=dynamic_element(&info->array,0,HASH_LINK*);
halfbuff= info->blength >> 1;
idx=first_index=info->records-halfbuff;
(idx != info->records)
/* If some records */
pos=data+idx;
hash_nr=rec_hashnr(info,pos->data);
(flag == 0)
/* First loop; Check if ok */
(my_hash_mask(hash_nr, info->blength, info->records) != first_index)
break
(!(hash_nr & halfbuff))
{
/* Key will not move */
(!(flag & LOWFIND))
(flag & HIGHFIND)
flag=LOWFIND | HIGHFIND;
/* key shall be moved to the current empty position */
gpos=empty;
ptr_to_rec=pos->data;
empty=pos;
/* This place is now free */
else
flag=LOWFIND | LOWUSED;
/* key isn't changed */
gpos=pos;
ptr_to_rec=pos->data;
else
(!(flag & LOWUSED))
/* Change link of previous LOW-key */
gpos->data=ptr_to_rec;
gpos->next= (uint) (pos-data);
flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
gpos=pos;
ptr_to_rec=pos->data;
else
{
/* key will be moved */
(!(flag & HIGHFIND))
flag= (flag & LOWFIND) | HIGHFIND;
/* key shall be moved to the last (empty) position */
gpos2 = empty; empty=pos;
ptr_to_rec2=pos->data;
else
(!(flag & HIGHUSED))
/* Change link of previous hash-key and save */
gpos2->data=ptr_to_rec2;
gpos2->next=(uint) (pos-data);
flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
gpos2=pos;
ptr_to_rec2=pos->data;
while
((idx=pos->next) != NO_RECORD);
((flag & (LOWFIND | LOWUSED)) == LOWFIND)
gpos->data=ptr_to_rec;
gpos->next=NO_RECORD;
((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
gpos2->data=ptr_to_rec2;
gpos2->next=NO_RECORD;
/* Check if we are at the empty position */
idx= my_hash_mask(rec_hashnr(info, record), info->blength, info->records + 1);
pos=data+idx;
(pos == empty)
pos->data=(uchar*) record;
pos->next=NO_RECORD;
else
/* Check if more records in same hash-nr family */
empty[0]=pos[0];
gpos= data + my_hash_rec_mask(info, pos, info->blength, info->records + 1);
(pos == gpos)
pos->data=(uchar*) record;
pos->next=(uint) (empty - data);
else
pos->data=(uchar*) record;
pos->next=NO_RECORD;
movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
(++info->records == info->blength)
info->blength+= info->blength;
return
(0);
size_t
maxlength)
((hashnr & (buffmax-1)) < maxlength)
return
(hashnr & (buffmax-1));
return
(hashnr & ((buffmax >> 1) -1));