Linux Certif

Toute la documentation sur la certification Linux LPI

hash

̾Á°

hash - hash ¥Ç¡¼¥¿¥Ù¡¼¥¹¤Ø¤Î¥¢¥¯¥»¥¹¥á¥½¥Ã¥É

½ñ¼°

#include <sys/types.h>

#include <db.h>

ÀâÌÀ

¥ë¡¼¥Á¥ó dbopen() ¤Ï¥Ç¡¼¥¿¥Ù¡¼¥¹¥Õ¥¡¥¤¥ë¤ËÂФ¹¤ë¥é¥¤¥Ö¥é¥ê¥¤¥ó¥¿¡¼¥Õ¥§¡¼¥¹¤Ç¤¢¤ë¡£ ¥µ¥Ý¡¼¥È¤µ¤ì¤Æ¤¤¤ë¥Õ¥¡¥¤¥ë¥Õ¥©¡¼¥Þ¥Ã¥È¤Î¤Ò¤È¤Ä¤Ë hash ¥Õ¥¡¥¤¥ë¤¬¤¢¤ë¡£ ¥Ç¡¼¥¿¥Ù¡¼¥¹¤Ø¤Î¥¢¥¯¥»¥¹¥á¥½¥Ã¥É¤Ë´Ø¤¹¤ë°ìÈÌŪ¤Êµ­½Ò¤Ï dbopen(3) ¤Ë½ñ¤«¤ì¤Æ¤¤¤ë¡£ ¤³¤Î¥Þ¥Ë¥å¥¢¥ë¥Ú¡¼¥¸¤Ç¤Ï hash ÆÃÍ­¤Î¾ðÊó¤Ë¤Ä¤¤¤Æ¤Î¤ßµ­½Ò¤¹¤ë¡£

hash ¥Ç¡¼¥¿¹½Â¤¤Ï¡¢³ÈÄ¥²Äǽ¤ÊưŪ¥Ï¥Ã¥·¥å¥¹¥­¡¼¥à¤Ç¤¢¤ë¡£

dbopen ¤ËÅϤµ¤ì¤ë hash ¥¢¥¯¥»¥¹¥á¥½¥Ã¥É¤ËÆÃÍ­¤Î¥Ç¡¼¥¿¹½Â¤ÂΤϡ¢ <db.h> ¥¤¥ó¥¯¥ë¡¼¥É¥Õ¥¡¥¤¥ë¤Ç°Ê²¼¤Î¤è¤¦¤ËÄêµÁ¤µ¤ì¤Æ¤¤¤ë¡£

typedef struct {

u_int bsize;
u_int ffactor;
u_int nelem;
u_int cachesize;
u_int32_t (*hash)(const void *, size_t);
int lorder;

} HASHINFO;

¤³¤Î¹½Â¤ÂΤÎÍ×ÁǤò°Ê²¼¤Ë¼¨¤¹¡£

bsize

bsize ¤Ï hash ¥Æ¡¼¥Ö¥ë¥Ð¥±¥Ã¥È (table bucket) ¤Î¥µ¥¤¥º¤òÄêµÁ¤¹¤ë¡£ ¥Ç¥Õ¥©¥ë¥È¤Ï 256 ¥Ð¥¤¥È¤Ç¤¢¤ë¡£ ¥Ç¥£¥¹¥¯¤ËÃÖ¤«¤ì¤ë¥Æ¡¼¥Ö¥ë¤ä¥Ç¡¼¥¿¥¢¥¤¥Æ¥à¤¬Â礭¤¤¥Æ¡¼¥Ö¥ë¤Ç¤Ï ¥Ú¡¼¥¸¥µ¥¤¥º¤òÂ礭¤¯¤¹¤ë¤Û¤¦¤¬Îɤ¤¤À¤í¤¦¡£

ffactor

ffactor ¤Ï¡¢¥æ¡¼¥¶¤¬Ë¾¤à hash ¥Æ¡¼¥Ö¥ëÃæ¤ÎÌ©Å٤Ǥ¢¤ë¡£ ¤³¤ì¤Ï¤½¤ì¤¾¤ì¤Î¥Ð¥±¥Ã¥È¤Ë³ÊǼ¤Ç¤­¤ë¥­¡¼¤Î³µ¿ô¤Ç¤¢¤ê¡¢ hash ¥Æ¡¼¥Ö¥ë¤ò³ÈÂ硦½Ì¾®¤òºîÍѤ¹¤ë¡£ ¥Ç¥Õ¥©¥ë¥È¤Ï 8 ¤Ç¤¢¤ë¡£

nelem

nelem ¤Ï hash ¥Æ¡¼¥Ö¥ë¤ÎºÇ½ª¥µ¥¤¥º¤òÂç¤Þ¤«¤Ë¸«ÀѤâ¤Ã¤¿ÃͤǤ¢¤ë¡£ ¤³¤ÎÃͤ¬¥»¥Ã¥È¤µ¤ì¤Æ¤¤¤Ê¤«¤Ã¤¿¤ê¡¢¤¢¤Þ¤ê¤ËÄ㤯¥»¥Ã¥È¤µ¤ì¤Æ¤¤¤ë¤È¡¢ hash ¥Æ¡¼¥Ö¥ë¤Ï¥­¡¼¤¬Æþ¤Ã¤Æ¤¯¤ë¤Ë±þ¤¸¤Æ³ÈÄ¥¤µ¤ì¤ë¡£ ¤·¤«¤·¾¯¤·¥Ñ¥Õ¥©¡¼¥Þ¥ó¥¹¤¬ (¤ª¤½¤é¤¯µ¤ÉÕ¤¯ÄøÅÙ¤Ë) Íî¤Á¤ë¡£ ¥Ç¥Õ¥©¥ë¥ÈÃÍ¤Ï 1 ¤Ç¤¢¤ë¡£

cachesize

¤³¤ÎÃÍ¤Ï ¤¢¤¯¤Þ¤Ç »²¹Í¤Ç¤¢¤ê¡¢¥¢¥¯¥»¥¹¥á¥½¥Ã¥É¤Ï¤³¤ÎÃͤò±Û¤¨¤¿¥á¥â¥ê¤Î ³ä¤êÅö¤Æ¤ËÀ®¸ù¤¹¤ë¤³¤È¤â¤¢¤ë¡£

hash

hash ¤Ï¥æ¡¼¥¶¡¼ÄêµÁ¤Î hash ´Ø¿ô¤Ç¤¢¤ë¡£ Á´¤Æ¤Î¥Ç¡¼¥¿¤ËÂФ·¤Æ¤¦¤Þ¤¯ºîÍѤ¹¤ë hash ´Ø¿ô¤È¸À¤¦¤Î¤Ï¤Ê¤¤¤«¤é¡¢ ÆÃÄê¤Î¥Ç¡¼¥¿¥»¥Ã¥È¤ËÂФ·¤Æ¤ÏÁȤ߹þ¤ß¤Î hash ´Ø¿ô¤Ç¤Ï ¥Ñ¥Õ¥©¡¼¥Þ¥ó¥¹¤¬Ä㤤¤³¤È¤â¤¢¤ë¤«¤â¤·¤ì¤Ê¤¤¡£ ¥æ¡¼¥¶¡¼ÄêµÁ¤Î hash ´Ø¿ô¤ÏÆó¤Ä¤Î°ú¿ô¤ò¤È¤é¤Ê¤¯¤Æ¤Ï¤Ê¤é¤Ê¤¤ (¥Ð¥¤¥Èʸ»ú Îó¤Ø¤Î¥Ý¥¤¥ó¥¿¤È¡¢Ä¹¤µ)¡£ ¤½¤·¤Æ hash ÃͤȤ·¤Æ»È¤ï¤ì¤ë 32¥Ó¥Ã¥È¤ÎÃͤòÊÖ¤µ¤Ê¤¯¤Æ¤Ï¤Ê¤é¤Ê¤¤¡£

lorder

¥Ç¡¼¥¿¥Ù¡¼¥¹¤Ë³ÊǼ¤µ¤ì¤Æ¤¤¤ë¥á¥¿¥Ç¡¼¥¿¤ÎÀ°¿ôÃͤΥХ¤¥È¥ª¡¼¥À¡¼¡£ ¤³¤Î¿ô»ú¤Ï¡¢½ç½ø¤òÀ°¿ô¤Çɽ¤·¤¿¤â¤Î¤Ç¤¢¤ë¡£ Î㤨¤Ð¥Ó¥Ã¥°¥¨¥ó¥Ç¥£¥¢¥ó¤Ê¤é¡¢¤³¤Î¿ôÃÍ¤Ï 4,321 ¤È¤Ê¤ë¡£ lorder ¤¬ 0 (»ØÄꤵ¤ì¤Æ¤¤¤Ê¤¤)¾ì¹ç¡¢¸½ºß¤Î¥Û¥¹¥È ¤Ç»È¤ï¤ì¤Æ¤¤¤ëʤӽ礬»È¤ï¤ì¤ë¡£ ¥Õ¥¡¥¤¥ë¤¬´û¤Ë¸ºß¤¹¤ë¾ì¹ç¡¢»ØÄꤷ¤¿ÃͤÏ̵»ë¤µ¤ì¥Ä¥ê¡¼¤¬ºî¤é¤ì ¤¿»þ¤Ë»ØÄꤵ¤ì¤Æ¤¤¤¿Ãͤ¬»È¤ï¤ì¤ë¡£

¥Õ¥¡¥¤¥ë¤¬´û¤Ë¸ºß¤·¤Æ¤¤¤ë (¤Þ¤¿¤Ï O_TRUNC ¥Õ¥é¥°¤¬»ØÄꤵ¤ì¤Æ¤¤¤Ê¤¤) ¤È¡¢ ¥Ñ¥é¥á¡¼¥¿ bsize, ffactor, lorder, nelem ¤Ë»ØÄꤵ¤ì¤¿¤Ï̵»ë¤µ¤ì¡¢ ¥Ï¥Ã¥·¥å¤¬ºî¤é¤ì¤¿»þ¤Ë»È¤Ã¤¿Ãͤ¬»È¤ï¤ì¤ë¡£

hash ´Ø¿ô¤¬»ØÄꤵ¤ì¤ë¤È¡¢ hash_open ¤Ï¥Ç¡¼¥¿¥Ù¡¼¥¹¤¬ºî¤é¤ì¤¿»þ¤Ë»ØÄꤵ¤ì¤Æ¤¤¤¿ hash ´Ø¿ô¤Èº£²ó»ØÄꤵ¤ì¤¿ hash ´Ø¿ô¤¬Æ±¤¸¤«¤É¤¦¤«¤òÄ´¤Ù¡¢ Ʊ¤¸¤Ç¤Ê¤¤¾ì¹ç¤Ë¤Ï¼ºÇÔ¤¹¤ë¡£

dbm(3), ¤È ndbm(3) ¤Ëµ­½Ò¤µ¤ì¤Æ¤¤¤ë¥ë¡¼¥Á¥ó¤Ø¤Î²áµî¸ß´¹¤ò¼è¤ë¤¿¤á¤Î¥¤¥ó¥¿¡¼¥Õ¥§¥¤¥¹¤¬ ¸ºß¤¹¤ë¡£¤·¤«¤·¤³¤ì¤é¤Î¥¤¥ó¥¿¡¼¥Õ¥§¥¤¥¹¤Ï°ÊÁ°¤Î¥Õ¥¡¥¤¥ë¥Õ¥©¡¼ ¥Þ¥Ã¥È¤È¤Ï¸ß´¹À­¤¬¤Ê¤¤¡£

¥¨¥é¡¼

hash ¥¢¥¯¥»¥¹¥á¥½¥Ã¥É¥ë¡¼¥Á¥ó¤Ï¡¢¼ºÇÔ¤¹¤ë¤È¥é¥¤¥Ö¥é¥ê¥ë¡¼¥Á¥ó dbopen(3) ¤Ç»ØÄꤵ¤ì¤Æ¤¤¤ë¥¨¥é¡¼¤Ë±þ¤¸¤¿ errno ¤ò¥»¥Ã¥È¤¹¤ë¡£

¥Ð¥°

¥Ð¥¤¥È¥ª¡¼¥À¡¼¤È¤·¤Æ¤Ï¥Ó¥Ã¥°¥¨¥ó¥Ç¥£¥¢¥ó¤È¥ê¥È¥ë¥¨¥ó¥Ç¥£¥¢¥ó¤Î¤ß¤¬ ¥µ¥Ý¡¼¥È¤µ¤ì¤Æ¤¤¤ë¡£

´ØÏ¢¹àÌÜ

btree(3), dbopen(3), mpool(3), recno(3)

Dynamic Hash Tables, Per-Ake Larson, Communications of the ACM, April 1988.

A New Hash Package for UNIX, Margo Seltzer, USENIX Proceedings, Winter 1991.