# 算法-散列表,算法-符号表的实现(顺序查找和二分查找)

## 拉链法

```@interface HashTable : NSObject

@property  (assign,nonatomic) NSInteger  count;//键值对总数

@property  (strong,nonatomic)  NSMutableArray  *sequenceTableArr;//存储顺序链表的数组

-(NSInteger)getHashCodeByKey:(NSString *)key;

-(void)putData:(NSString *)key value:(NSString *)value;

-(NSString *)getValue:(NSString *)key;

@end
```

实现代码:

```@implementation HashTable

self=[super init];
if (self) {
SequenceTable *sequenceTable;
for (NSInteger i=0; i<linkCount; i++) {
sequenceTable=[[SequenceTable alloc]init];
}
}
return self;
}

-(NSMutableArray *)sequenceTableArr{
if (!_sequenceTableArr) {
_sequenceTableArr=[[NSMutableArray alloc]initWithCapacity:1];
}
return _sequenceTableArr;
}

-(NSInteger)getHashCodeByKey:(NSString *)key{
NSInteger  value=[key integerValue];
}

-(void)putData:(NSString *)key value:(NSString *)value{
NSInteger index=[self getHashCodeByKey:key];
SequenceTable  *table =self.sequenceTableArr[index];
[table put:key value:value];
}

-(NSString *)getValue:(NSString *)key{
NSInteger index=[self getHashCodeByKey:key];
SequenceTable  *table =self.sequenceTableArr[index];
return [table get:key];
}
@end
```

测试代码:

```        HashTable  *hashTable=[[HashTable alloc]initWithData:5];
[hashTable putData:@"3" value:@"FlyElephant"];
[hashTable putData:@"5" value:@"原文地址:http://www.cnblogs.com/xiaofeixiang"];
[hashTable putData:@"2" value:@"博客园"];
[hashTable putData:@"1" value:@"技术交流:228407086"];
[hashTable putData:@"7" value:@"keso"];
[hashTable putData:@"8" value:@"上海"];
[hashTable putData:@"9" value:@"北京"];
[hashTable putData:@"10" value:@"深圳"];
NSString  *temp=[hashTable getValue:@"5"];
NSLog(@"keso:%@",temp);
```

## 线性探测法

```@interface LinearHashTable : NSObject

-(instancetype)initWithData:(NSInteger)capcity;

@property (assign,nonatomic) NSInteger  count;//符号表中键值对的总数

@property (assign,nonatomic) NSInteger  capticity;//数组的大小

@property (strong,nonatomic) NSMutableArray *keys;

@property (strong,nonatomic) NSMutableArray *values;

-(NSInteger)getHashCodeByKey:(NSString *)key;

-(void)putData:(NSString *)key value:(NSString *)value;

-(NSString *)getValue:(NSString *)key;

@end　　```

```@implementation LinearHashTable

-(instancetype)initWithData:(NSInteger)capcity{
self=[super init];
if (self) {
self.capticity=capcity;
for (NSInteger i=0;i<capcity;i++) {
}
}
return self;
}

-(NSMutableArray *)keys{
if (!_keys) {
_keys=[[NSMutableArray alloc]initWithCapacity:self.capticity];
}
return _keys;
}

-(NSMutableArray *)values{
if (!_values) {
_values=[[NSMutableArray alloc]initWithCapacity:self.capticity];
}
return _values;
}

-(void)resize:(NSInteger)capcity{
LinearHashTable  *table=[[LinearHashTable alloc]initWithData:capcity];
for (NSInteger i=0;i<self.capticity; i++) {
if (self.keys[i]!=[NSNull null]) {
[table putData:self.keys[i] value:self.values[i]];
}
}
self.keys=table.keys;
self.values=table.values;
self.capticity=table.capticity;
}

-(NSInteger)getHashCodeByKey:(NSString *)key{
return [key integerValue]%self.capticity;
}

-(void)putData:(NSString *)key value:(NSString *)value{
if (self.count>=self.capticity/2) {
[self resize:self.capticity*2];
}
NSInteger i;
for (i=[self getHashCodeByKey:key];self.keys[i]!=[NSNull null];i=(i+1)%self.capticity) {
if ([self.keys[i] isEqualToString:key]) {
self.values[i]=value;
return;
}
}
self.keys[i]=key;
self.values[i]=value;
self.count=self.count+1;
}

-(NSString *)getValue:(NSString *)key{
for (NSInteger i=[self getHashCodeByKey:key]; self.keys[i]!=NULL; i=(i+1)%self.capticity) {
if ([self.keys[i] isEqualToString:key]) {
return self.values[i];
}
}
return NULL;
}

@end```

相比上面的拉链法，此处多了一个resize，以免N接近于M的时候效率很低，N最好小于M的1/2~

```        LinearHashTable  *hashTable=[[LinearHashTable alloc]initWithData:12];
[hashTable putData:@"2" value:@"FlyElephant"];
[hashTable putData:@"3" value:@"原文地址:http://www.cnblogs.com/xiaofeixiang"];
[hashTable putData:@"15" value:@"博客园"];
[hashTable putData:@"6" value:@"技术交流:228407086"];
[hashTable putData:@"9" value:@"keso"];
[hashTable putData:@"12" value:@"FlyElephant"];
[hashTable putData:@"13" value:@"北京"];
NSString  *temp=[hashTable getValue:@"12"];
NSLog(@"博客园:%@",temp);```

原文作者：Fly_Elephant
原文地址: https://www.cnblogs.com/xiaofeixiang/p/4677285.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。