专业程序代写(QQ:928900200)
Implement a HashSet class for elements of type string.
It has the following functions:
bool add(const string &)
bool contains(const string &) const
int size() const
In this exercise, you need to implement some of the above functions, as well as several internal functoins:
int find(const string & e) const
void resize(int capacity2)
bool contains(const string & e) const
Hint:
The function find(e) finds the first position starting from p=h%N, which is either empty or equal to e. That is, find(e) should look like the following:
int find(const string & e) const {
int p = hashIndex(e);
while (true) {
if (…) return p;
p = (p + 1) % capacity;
}
}
EXAMPLE INPUT
apple
orange
banana
apple
orange
apple
watermelonEXAMPLE OUTPUT
3
true
false
主程序
#include <iostream>
#include <string>
using namespace std;
//////////////////////////
// Interfaces
//
template <typename E>
class Set
{
public:
virtual bool add(const E &) = 0;
virtual bool contains(const E &) const = 0;
virtual int size() const = 0;
};
template <typename E>
class HashFunction
{
public:
virtual int getHashCode(const E & e) const = 0;
};
/////////////////////////
// hash-function
//
class StringHashFunction : public HashFunction<string>
{
public:
int getHashCode(const string & text) const {
int code = 0;
for (int i = 0; i < text.size(); ++ i) {
int code1 = text[i];
code1 = code1 « (i * 8 % 24);
code = code ^ code1;
}
return code;
}
};
/////////////////////////
// your class
//
class HashSet : public Set<string>
{
private:
const StringHashFunction hashFunction;
class Entry
{
public:
string element;
bool isInUse;
Entry() {
isInUse = false;
}
};
Entry * entries;
int capacity;
int count;
void initialize(int capacity2) {
count = 0;
capacity = capacity2;
entries = new Entry[capacity];
}
void assign(const HashSet & set2) {
count = set2.count;
capacity = set2.capacity;
entries = new Entry[capacity];
for (int i = 0; i < capacity; ++ i) {
entries[i] = set2.entries[i];
}
}
public:
HashSet() {
initialize(2);
}
~HashSet() {
delete [] entries;
}
HashSet(const HashSet & set2) {
assign(set2);
}
HashSet & operator = (const HashSet & set2) {
delete [] entries;
assign(set2);
return (*this);
}
private:
int hashIndex(const string & e) const {
int hashCode = hashFunction.getHashCode(e);
return hashCode % capacity;
}
int find(const string & e) const;
void resize(int capacity2);
public:
bool add(const string & e) {
int index = find(e);
if (entries[index].isInUse) {
return false;
}
entries[index].element = e;
entries[index].isInUse = true;
++ count;
if (count > capacity / 2) {
resize(capacity * 2);
}
return true;
}
bool contains(const string & e) const;
int size() const {
return count;
}
};
#include “source”
int main() {
HashSet set;
for (int i = 0; i < 5; ++ i) {
string text;
cin » text;
set.add(text);
}
cout « set.size() « endl;
for (int i = 0; i < 2; ++ i) {
string text;
cin » text;
if (set.contains(text)) {
cout « “true” « endl;
}
else {
cout « “false” « endl;
}
}
}
相关推荐
c++一个用vector实现java的HashSet集合类,可以将任何类,数字,字符串,vector等等存放到里面
HashSet的实现原理 ,HashSet与HashMap的区别 以及 HashSet的底层实现方式
这个是关于java语言的hashset集合类的一些基本用法和详解了个方法的使用
Class005_HashSet.java
对于 HashSet 而言,它是基于 HashMap 实现的,HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下代码:
hash_set c++总结(自定义类型stuct、class)。总结自定义struct、class三个案例。find函数测试,hash_set迭代器。
简述了HashSet去重原理
源码解析jdk7.0集合:HashSet的底层实现原理.pdf
java HashSet 集合排序,需要通过利用TreeSet集合排序。2013-10-30。
Set是java中一个不包含重复元素的collection。更正式地说,set 不包含满足e1....HashSet与TreeSet都是基于Set接口的实现类。其中TreeSet是Set的子接口SortedSet的实现类。Set接口及其子接口、实现类的结构如下所示。
随机数,HsahSet,排序,输出.随机数,HsahSet,排序,输出.
hashSet底层去重原理
它是由HashMap实现的,不保证元素的顺序,而且HashSet允许使用 null 元素。 HashSet是非同步的。如果多个线程同时访问一个哈希 set,而其中至少一个线程修改了该 set,那么它必须 保持外部同步。
hashset.js 简单的哈希集实现,旨在与前端上的数据库条目一起使用。 如果它具有主键,则将其存储在哈希集中可能是一个好主意。安装 jspm i npm:hashset.jsnpm i hashset.js为什么不设置es6? 因为它不适用于数据库...
treemap treeset hashset hashmap 简要介绍
HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别。HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)...
HashSet 是 Java 中的一个集合类,它实现了 Set 接口并提供了基于哈希表的无序、不重复元素的集合。具体来说,它是通过哈希表(实际上是一个 HashMap 实例)来存储元素的。 以下是 HashSet 的一些主要特点: 无序...
20220424-笔记-HashSet扩容机制
Qt4.8.5 Bug Patch File
源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556