【C算法】第3章 探索 (その2)

こつこつ。今日は「3-4 ハッシュ法」から。

• このハッシュ法のところ、パタヘネの記憶階層のキャッシュのところと関連が強いな。
  
• うーん。。。ポインタのポインタがいまいちしっくりこない。Node **pp = &h->table[key];とか。
  
  
  
  • まず、typedef struct { int size; Node **table; } Hash; なので、Hashはここで定義した構造体の型をあらわすシンボルであり、Hash型のオブジェクトには、Hash h;なときはh.hash, Hash *hなときはh->tableにてアクセスできるオブジェクトが含まれている。ここで、tableはHash型の内部要素に対するシンボルであり、型は(Node **)である。
    
  • さて、Node型について。typedef struct __node { Data data; struct __node *next; } Node;なので、Nodeはこれまたシンボルであり型をあらわしている。Nodeは__nodeの別名である。__node型は自己参照している構造体であり、Node n;のとき、n.nextは(Node *)型である。
    
  • ここで、tableとかnextとかのシンボルは、誰が所有しているのかという疑問がある。おそらく、型の定義として処理系のどこかで一元管理されているのだろう。
    
  • そして、シンボル管理機構では、シンボルと型とメモリ領域に関する情報が管理されている、と。
    
  • なので、Node型のnextというのは型定義がもっており、Node n;としたときに(n,Node, <メモリアドレス>)というシンボル管理には含まれない。
    
  • さて、Node n;のとき、n.nextはNode型の定義を参照して、シンボルnのメモリ領域の後半部分に格納されている値を指すことになる。すると、その値の型は何かという話題がある。それはNode型の定義に記述されており、(Node *)型という。*が付く型はメモリアドレスを値としてもつ。このメモリアドレスが指すメモリ領域はNode型として解釈可能なものとなるようにプログラマはメモリを構成しなければいけない。(ただしNULLも許容するものとする)
    
  • そのことを前提にすると、n.next != NULLのとき、*n.nextによって、n.nextの値にあるメモリ領域についてそれをNode型としてアクセスできる。このとき、そのメモリ領域は、別途 Node n1;などとして構成されたもの、すなわちシンボル管理機構でシンボルとともに登録されているものでもよいし、callocなどで確保されただけの単なるメモリ領域でもよい。
    
  • さて、Hash型に戻る。Hash h;のとき、h.tableは、シンボル管理、(h,Hash,<メモリアドレス>)を起点に処理される｡Hash型の定義の中に、tableは(Node **)型であることが記載されている。*がついてるのでこれもメモリアドレスを値としてもつ。ただし2つあるので、このメモリアドレスに格納されているのもメモリアドレスであり、その先にあるのがNode型で処理できるメモリ領域であるということ。
    
  • ここまでの整理にて、Node **pp = &h->table[key];が理解できるか。
    
  • まず、Node **ppは、(pp, (Node **), とあるメモリアドレス)を意味する。初期化子として式が記載されているので、そのメモリアドレスに格納する値もこの式できまる。
    
  • 値について。&(h->table[key])が何かということ。Hash *hなので、h->tableによって、どこかのメモリ領域をHash型として処理して、そこのtable該当領域の値を指すことになる。table該当領域の型は(Node **)なので、table該当領域の値はメモリアドレスである。
    
  • table[key]演算は、*(*table + key)と同じである。*(*table + key)は、tableが指すメモリ領域が、型Aの配列的な構造であることを期待しており、その先頭アドレスがtableであるところ、先頭Aから型Aの大きさにてkey個分さきのもののメモリアドレスに格納されている値という意味である。
    
  • よって、[key]によって、h->table[key]は(Node *)型であるとしてのメモリアドレスに格納されている値に該当する。
    
  • う、やっぱりわからない。
    
  
  
• 一応、ハッシュ法は理解したが、ポインタがやっぱりわからない。。。
  

こつこつ。