Last active
October 22, 2025 07:31
-
-
Save saeedvir/9f2076b8257c579e49647a95ddc6708e to your computer and use it in GitHub Desktop.
php Cuckoo Filter
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| class CuckooFilter | |
| { | |
| protected int $bucketCount; | |
| protected int $bucketSize; | |
| protected array $buckets; | |
| protected int $maxKick; // برای جلوگیری از حلقه بیپایان | |
| public function __construct(int $bucketCount = 64, int $bucketSize = 4, int $maxKick = 500) | |
| { | |
| $this->bucketCount = $bucketCount; | |
| $this->bucketSize = $bucketSize; | |
| $this->maxKick = $maxKick; | |
| $this->buckets = array_fill(0, $bucketCount, []); | |
| } | |
| protected function fingerprint(string $item): string | |
| { | |
| // fingerprint کوچک (مثلاً 8 بیت) | |
| return substr(md5($item), 0, 2); | |
| } | |
| protected function index1(string $item): int | |
| { | |
| return crc32($item) % $this->bucketCount; | |
| } | |
| protected function index2(int $index1, string $fingerprint): int | |
| { | |
| // index جایگزین | |
| return ($index1 ^ (crc32($fingerprint))) % $this->bucketCount; | |
| } | |
| public function insert(string $item): bool | |
| { | |
| $fp = $this->fingerprint($item); | |
| $i1 = $this->index1($item); | |
| $i2 = $this->index2($i1, $fp); | |
| if (count($this->buckets[$i1]) < $this->bucketSize) { | |
| $this->buckets[$i1][] = $fp; | |
| return true; | |
| } | |
| if (count($this->buckets[$i2]) < $this->bucketSize) { | |
| $this->buckets[$i2][] = $fp; | |
| return true; | |
| } | |
| // در غیر این صورت، "کیک" یا جابجایی | |
| $i = (rand(0, 1) === 0) ? $i1 : $i2; | |
| for ($n = 0; $n < $this->maxKick; $n++) { | |
| $r = rand(0, count($this->buckets[$i]) - 1); | |
| $evicted = $this->buckets[$i][$r]; | |
| $this->buckets[$i][$r] = $fp; | |
| $i = $this->index2($i, $evicted); | |
| if (count($this->buckets[$i]) < $this->bucketSize) { | |
| $this->buckets[$i][] = $evicted; | |
| return true; | |
| } | |
| $fp = $evicted; | |
| } | |
| return false; // جدول پر شده است | |
| } | |
| public function contains(string $item): bool | |
| { | |
| $fp = $this->fingerprint($item); | |
| $i1 = $this->index1($item); | |
| $i2 = $this->index2($i1, $fp); | |
| return in_array($fp, $this->buckets[$i1]) || in_array($fp, $this->buckets[$i2]); | |
| } | |
| public function delete(string $item): bool | |
| { | |
| $fp = $this->fingerprint($item); | |
| $i1 = $this->index1($item); | |
| $i2 = $this->index2($i1, $fp); | |
| if (($key = array_search($fp, $this->buckets[$i1])) !== false) { | |
| unset($this->buckets[$i1][$key]); | |
| return true; | |
| } | |
| if (($key = array_search($fp, $this->buckets[$i2])) !== false) { | |
| unset($this->buckets[$i2][$key]); | |
| return true; | |
| } | |
| return false; | |
| } | |
| } | |
| // ---------------------------- | |
| // مثال استفاده | |
| // ---------------------------- | |
| $cf = new CuckooFilter(); | |
| $cf->insert('apple'); | |
| $cf->insert('banana'); | |
| echo "apple? " . ($cf->contains('apple') ? '✅ وجود دارد' : '❌ ندارد') . PHP_EOL; | |
| echo "orange? " . ($cf->contains('orange') ? '✅ وجود دارد' : '❌ ندارد') . PHP_EOL; | |
| $cf->delete('banana'); | |
| echo "banana after delete? " . ($cf->contains('banana') ? '✅' : '❌ حذف شد') . PHP_EOL; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment