FilesExpand file tree

 master

/

SimpleBloomFilter.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

106 lines (87 loc) · 2.28 KB

 master

/

SimpleBloomFilter.java

Copy path

Top

File metadata and controls

• Code
• Blame

106 lines (87 loc) · 2.28 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

package SimpleBloomFilter;

/**

* 一个BloomFilter的简单实现

* 只能添加，不能删除元素；不存在则一定不存在；存在只是大概率有可能存在(与Hash函数个数、数组长度有关)；

*/

public class SimpleBloomFilter {

//数组长度

private int arraySize;

//数组

private boolean[] array;

//构造函数

public SimpleBloomFilter(int arraySize) {

this.arraySize = arraySize;

array = new boolean[arraySize];

}

/**

* 写入数据

* @param key

*/

public void add(String key) {

array[hashcode_1(key) % arraySize] = true;

array[hashcode_2(key) % arraySize] = true;

array[hashcode_3(key) % arraySize] = true;

}

/**

* 判断数据是否可能存在

* @param key

* @return

*/

public boolean check(String key) {

if(array[hashcode_1(key) % arraySize] == false)

return false;

if(array[hashcode_2(key) % arraySize] == false)

return false;

if(array[hashcode_3(key) % arraySize] == false)

return false;

return true;

}

/**

* hash 算法1

* @param key

* @return

*/

private int hashcode_1(String key) {

int hash = 0;

int i;

for (i = 0; i < key.length(); ++i) {

hash = 33 * hash + key.charAt(i);

}

return Math.abs(hash);

}

/**

* hash 算法2

* @param data

* @return

*/

private int hashcode_2(String data) {

final int p = 16777619;

int hash = (int) 2166136261L;

for (int i = 0; i < data.length(); i++) {

hash = (hash ^ data.charAt(i)) * p;

}

hash += hash << 13;

hash ^= hash >> 7;

hash += hash << 3;

hash ^= hash >> 17;

hash += hash << 5;

return Math.abs(hash);

}

/**

* hash 算法3

* @param key

* @return

*/

private int hashcode_3(String key) {

int hash, i;

for (hash = 0, i = 0; i < key.length(); ++i) {

hash += key.charAt(i);

hash += (hash << 10);

hash ^= (hash >> 6);

}

hash += (hash << 3);

hash ^= (hash >> 11);

hash += (hash << 15);

return Math.abs(hash);

}

}