コンシステントハッシュ法
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2013/06/17 07:57 UTC 版)
コンシステントハッシュ法 (Consistent hashing) はスロットの追加や削除に対して、最小限のキーのスロットへのマッピングの変更で、ハッシュテーブルの機能を提供することのできる特殊なハッシュ法。その他多くのハッシュテーブルでは、スロット数の変化はほぼすべてのキーが再マッピングされるのに対して、コンシステントハッシュの場合、K をキーの数、n をスロット数とすると、平均 K / n 個のキーの再マップですむ。分散システムの一形態である分散キャッシュなどで利用されている。
|
- ^ Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. (1997). “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA. pp. 654–663. doi:10.1145/258533.258660 2008年6月17日閲覧。
- ^ Doi, Katsuo. “Super Proxy Script - How to make distributed proxy servers by URL hashing”. 2011年8月4日閲覧。
- ^ Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). “Web Caching with Consistent Hashing”. Computer Networks 31 (11): 1203–1213. doi:10.1016/S1389-1286(99)00055-9 2008年6月17日閲覧。.
- 1 コンシステントハッシュ法とは
- 2 コンシステントハッシュ法の概要
- 3 外部リンク
- コンシステントハッシュ法のページへのリンク