集合结构

无序，不能通过下标值进行访问
不能重复，相同的数据只会存在一份
ES6包含Set类即为集合 4.集合的封装

function Set(){
	this.item={}
  //添加方法
  Set.prototype.add=function(data){
  	if(this.item.has(data)) return false
    this.item[data]=data
    return true
  }
  //包含方法
  Set.prototype.has=function(data){
  	return this.item.hasOwnprototype(data)
  }
  //删除方法
  Set.prototype.remove=function(data){
  	if(!this.item.has(data)) return false
    delete this.item[data]
    return true
  }
  //清除方法
  Set.prototype.clear=function(){
  	this.item={}
  }
  //长度方法
  Set.prototype.size=function(){
  	return Object.keys(this.item).length
  }
  Set.prototype.value=function(){
  	return Object.keys(this.item)
  }
}

集合间操作

并集

Set.prototype.union=function(otherSet){
	var unionSet=new Set()
    var value=this.value
    for(let i=0;i<value.length;i++){
    	unionSet.add(value[i])
    }
  	value=otherSet.value
  	for(let j=0;j<value.length;j++){
    	unionSet.add(value[j])
    }
  return unionSet
}

交集

Set.prototype.intersection=function(otherSet){
	var intersection=new Set()
    var value=this.value
    for(let i;i<value.length;i++){
    	if(otherSet.has(value[i])){
        	intersection.add(value[i])
        }
    }
  	return intersection 
}

差集

Set.prototype.difference=function(otherSet){
	var difference=new Set()
    var value=this.value
    for(let i=0;i<value.length;i++){
    	if(!otherSet.has(value[i])){
        	difference.add(value[i])
        }
    }
  	return difference
}

子集

Set.prototype.subset=function(otherSet){
	var value=otherSet.value
    for(let i=0;i<value.length;i++){
    	if(!this.has(value[i])){
        	return false
        }
    }
  	return true
}

集合结构

一一对应的键值对
key不可以重复，value可以重复，key是无序的
字典和映射

python称映射关系为字典
Java称映射关系为Map

哈希表结构

哈希表可以提供非常快速地插入-删除-查找操作，接近O（1）的时间级
速度比树快，编码比树容易
数据没有顺序，不能以固定顺序来遍历
通常情况下，key值不允许重复
结构是数组，但特点在于下标值的变化，哈希函数
哈希化：将大数字转化为数组范围内下标的过程，称之为哈希化
哈希函数：将单词转换成大数字，大数字再进行哈希化的代码实现放在一个函数中，这个函数称为哈希函数
哈希表：最终将数据插入到的数组，并对结构进行封装，称之为一个哈希表
冲突：哈希化后下标一样，冲突不可避免，只能解决

链地址法（拉链法） (1)每个数据单元存储的不是一个数据，而是一个链条 (2)链条的数据结构可以是数组或者链表
开放地址法 (1)寻找空白的单元格来添加重复的数据 (2)线性探测：从哈希化得到的位置不断加一（x+1，x+2）找空的位置 (3)二次探测：基于线性探测，对步长做了优化(x+1^2,x+2^2),一次性探测较长距离 (4)再哈希法：把关键字用另一个哈希函数再做一次哈希化，并以此结果作为步长
装填因子包含的数据项与整个哈希表长度的比值 (1)开发地址法装填因子最大为1 (2)链地址法装填因子可以大于1，效率低

哈希函数封装

function hashFunc(str,size){
	var hashcode=0
    //霍纳算法，计算hashcode值
    for(let i=0;i<str.length;i++){
    	hashcode=37*hashcode+str.charCodeAt(i)
    }
  //取余
  	var index=hashcode % size
    return index
}

质数判断

function isPrime(num){
	var temp=parseInt(Math.sqrt(num))
    for(let i=0;i<=temp;i++){
    	if(num%i==0){
        	return false
        }
    }
  	return true
}
function getPrime(num){
	while(!thi.isPrime(num)){
    	num++
    }
  	return num
}

哈希表的封装

function HashTable=function(){
	this.storage=[]
  	this.count=0
  	this.limit=7
  //插入和修改
  HashTable.prototype.put=function(key,value){
  	var index=this.hashFunc(key,this.limit)
    var bucket=this.storage[index]
    if(bucket==null){
    	bucket=[]
      	this.storage[index]=bucket
    }
    for(let i=0;i<bucket.length;i++){
    	if(bucket[i][0]==key){
        	bucket[i][1]=value
          this.count++
          	return
        }
    }
    bucket.push([key,value])
    this.count++
    //判断是否扩容
    if(this.count>this.limit*0.75){
    	this.resize(this.limit*2)
    }
    return
  }
  //查找获取方法
  HashTable.prototype.get=function(key){
  	var index=this.hashFunc(key,this.limit)
    var bucket=this.storage[index]
    if(bucket==null) return null
    for(let i=0;i<bucket.length;i++){
    	if(bucket[i][0]==key){
        	return bucket[i][1]
        }
    }
    return null
  }
  //删除方法
  HashTable.prototype.remove=function(key){
  	var index=this.hashFunc(key,this.limit)
    var bucket=this.storage[index]
    if(bucket==null) return null
    for(let i=0;i<bucket.length;i++){
    	if(bucket[i][0]==key){
          var tuple=bucket[i][1]
        	bucket.splice(i,1)
          	this.count--
          	return tuple
        }
    }
    return null
  }
  //扩容
  HashTable.prototype.resize=function(newlimit){
  	var oldstorage=this.storage
    this.storage=[]
    this.count=0
    
    this.limit=this.getPrime(newlimit)
    for(let i=0;i<oldstorage.length;i++){
      	var bucket=oldstorage[i]
    	if(bucket==null){
        	continue
        }
      	for(let j=0;j<bucket.length;j++){
        	this.put(bucket[i][0],bucket[i][1])
        }
    }
  }
}

数据结构学习笔记（二）

集合结构

集合结构

哈希表结构