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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
| /**
* Redis Set类型的IntSet实现
* 当集合只包含整数且元素较少时使用
*/
public class IntSet {
private static final int INTSET_ENC_INT16 = 2; // 16位整数
private static final int INTSET_ENC_INT32 = 4; // 32位整数
private static final int INTSET_ENC_INT64 = 8; // 64位整数
private int encoding; // 编码方式
private int length; // 元素个数
private byte[] contents; // 存储数组
public IntSet() {
this.encoding = INTSET_ENC_INT16; // 默认使用16位
this.length = 0;
this.contents = new byte[0];
}
/**
* 根据值确定所需的编码
* @param value 整数值
* @return 编码类型
*/
private int getEncodingForValue(long value) {
if (value >= Short.MIN_VALUE && value <= Short.MAX_VALUE) {
return INTSET_ENC_INT16;
} else if (value >= Integer.MIN_VALUE && value <= Integer.MAX_VALUE) {
return INTSET_ENC_INT32;
} else {
return INTSET_ENC_INT64;
}
}
/**
* 升级编码并插入新值
* @param value 新值
*/
private void upgradeAndAdd(long value) {
int oldEncoding = encoding;
int newEncoding = getEncodingForValue(value);
System.out.println("IntSet编码升级: " + oldEncoding + " -> " + newEncoding);
// 创建新的contents数组
byte[] newContents = new byte[(length + 1) * newEncoding];
// 根据新值的大小决定插入位置
boolean insertAtEnd = value > 0;
int insertPos = insertAtEnd ? length : 0;
// 复制并转换现有元素
for (int i = 0; i < length; i++) {
long oldValue = getValue(i, oldEncoding);
int newPos = insertAtEnd ? i : i + 1;
setValue(newContents, newPos, oldValue, newEncoding);
}
// 插入新值
setValue(newContents, insertPos, value, newEncoding);
// 更新IntSet状态
this.encoding = newEncoding;
this.contents = newContents;
this.length++;
}
/**
* 从指定位置获取值
* @param pos 位置
* @param encoding 编码方式
* @return 值
*/
private long getValue(int pos, int encoding) {
if (encoding == INTSET_ENC_INT16) {
short value = (short) ((contents[pos * 2] & 0xFF) |
((contents[pos * 2 + 1] & 0xFF) << 8));
return value;
} else if (encoding == INTSET_ENC_INT32) {
int value = (contents[pos * 4] & 0xFF) |
((contents[pos * 4 + 1] & 0xFF) << 8) |
((contents[pos * 4 + 2] & 0xFF) << 16) |
((contents[pos * 4 + 3] & 0xFF) << 24);
return value;
} else {
// INT64处理类似但更复杂，这里简化
return 0;
}
}
/**
* 在指定位置设置值
* @param array 数组
* @param pos 位置
* @param value 值
* @param encoding 编码方式
*/
private void setValue(byte[] array, int pos, long value, int encoding) {
if (encoding == INTSET_ENC_INT16) {
array[pos * 2] = (byte) (value & 0xFF);
array[pos * 2 + 1] = (byte) ((value >> 8) & 0xFF);
} else if (encoding == INTSET_ENC_INT32) {
array[pos * 4] = (byte) (value & 0xFF);
array[pos * 4 + 1] = (byte) ((value >> 8) & 0xFF);
array[pos * 4 + 2] = (byte) ((value >> 16) & 0xFF);
array[pos * 4 + 3] = (byte) ((value >> 24) & 0xFF);
}
// INT64类似处理
}
/**
* 二分查找元素位置
* @param value 要查找的值
* @return 位置，如果不存在返回负数
*/
private int search(long value) {
int min = 0, max = length - 1, mid = -1;
if (length == 0) {
return 0;
}
// 检查边界
if (value > getValue(max, encoding)) {
return length; // 插入到末尾
} else if (value < getValue(0, encoding)) {
return 0; // 插入到开头
}
// 二分查找
while (max >= min) {
mid = (min + max) / 2;
long current = getValue(mid, encoding);
if (current == value) {
return mid; // 找到了
} else if (current < value) {
min = mid + 1;
} else {
max = mid - 1;
}
}
return min; // 插入位置
}
/**
* 添加元素
* @param value 要添加的值
* @return 是否添加成功
*/
public boolean add(long value) {
int requiredEncoding = getEncodingForValue(value);
// 如果需要升级编码
if (requiredEncoding > encoding) {
upgradeAndAdd(value);
return true;
}
int pos = search(value);
if (pos < length && getValue(pos, encoding) == value) {
return false; // 元素已存在
}
// 扩展数组
byte[] newContents = new byte[(length + 1) * encoding];
// 复制元素并插入新值
for (int i = 0; i < pos; i++) {
setValue(newContents, i, getValue(i, encoding), encoding);
}
setValue(newContents, pos, value, encoding);
for (int i = pos; i < length; i++) {
setValue(newContents, i + 1, getValue(i, encoding), encoding);
}
this.contents = newContents;
this.length++;
return true;
}
/**
* 检查元素是否存在
* @param value 要检查的值
* @return 是否存在
*/
public boolean contains(long value) {
int requiredEncoding = getEncodingForValue(value);
if (requiredEncoding > encoding) {
return false; // 编码不匹配，肯定不存在
}
int pos = search(value);
return pos < length && getValue(pos, encoding) == value;
}
/**
* 获取集合大小
* @return 集合大小
*/
public int size() {
return length;
}
/**
* 获取所有元素
* @return 元素列表
*/
public List<Long> getAllElements() {
List<Long> elements = new ArrayList<>();
for (int i = 0; i < length; i++) {
elements.add(getValue(i, encoding));
}
return elements;
}
/**
* 演示IntSet的使用
*/
public static void demonstrateIntSet() {
System.out.println("=== IntSet演示 ===");
IntSet intSet = new IntSet();
// 添加16位整数
System.out.println("添加16位整数...");
intSet.add(1);
intSet.add(10);
intSet.add(100);
System.out.println("当前编码: " + intSet.encoding);
System.out.println("元素: " + intSet.getAllElements());
// 添加32位整数，触发编码升级
System.out.println("\n添加32位整数...");
intSet.add(100000);
System.out.println("当前编码: " + intSet.encoding);
System.out.println("元素: " + intSet.getAllElements());
// 测试查找
System.out.println("\n查找测试:");
System.out.println("包含10: " + intSet.contains(10));
System.out.println("包含50: " + intSet.contains(50));
}
}
|