什么是哈希hash 算法
哈希(Hash)表
一般的查找方法基于比较的,查找效率依赖比较次数,其实理想的查找希望不经比较,一次存取便能得到所查
记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,这样查找k时,只要根据这个
对应关系f找到给定值k的像f(k)。这种对应关系f叫哈希(hash)函数。按这种思想建立的表叫哈希表(也
叫散列表)。哈希表存取方便但存储时容易冲突(collision):即不同的关键字可以对应同一哈希地址。如
何确定哈希函数和解决冲突是关键。
1.哈希函数的构造方法
直接定址法:H(k)=k 或H(k)=a*k+b(线形函数)
如:人口数字统计表
地址 1 2 3 ... 100
年龄 1 2 3 ... 100
人数 67 3533 244 ... 4
数字分析法:取关键字的若干数位组成哈希地址
如:关键字如下:若哈希表长为100则可取中间两位10进制数作为哈希地址。
81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537
平方取中法:关键字平方后取中间几位数组成哈希地址
折叠法:将关键数字分割成位数相同的几部分(最后一部分的位数可以不同)然后取几部分的叠加和(舍
去进位)作为哈希地址。
除留余数法:取关键字被某个不大于表长m的数p除后所得的余数为哈希地址。
H(k)=k mod p p<=m
随机数法:H(k)=rondom(k)。
2.处理冲突的方法
假设地址集为0..n-1,由关键字得到的哈希地址为j(0<=j<=n-1)的位置已存有记录,处理冲突就是为该关键
字的记录找到另一个"空"的哈希地址。在处理中可能得到一个地址序列Hi i=1,2,...k
0<=Hi<=n-1),即在处理冲突时若得到的另一个哈希地址H1仍发生冲突,再求下一地址H2,若仍冲突,再求
H3...。怎样得到Hi呢?
开放定址法:Hi=(H(k)+di) mod m (H(k)为哈希函数;m为哈希表长;di为增量序列)
当di=1,2,3,... m-1 时叫线性探测再散列。
当di=12,-12,22,-22,32,-32,...,k2,-k2时叫二次探测再散列。
当di=random(m)时叫伪随机探测序列。
例:长度为11的哈希表关键字分别为17,60,29,哈希函数为H(k)=k mod 11,第四个记录的关键字为38
,分别按上述方法添入哈希表的地址为8,4,3(随机数=9)。
再哈希法:Hi=RHi(key) i=1,2,...,k,其中RHi均为不同的哈希函数。
链地址法:这种方法很象基数排序,相同的地址的关键字值均链入对应的链表中。
建立公益区法:另设一个溢出表,不管得到的哈希地址如何,一旦发生冲突,都填入溢出表。
3.哈希表的查找
例:如下一组关键字按哈希函数H(k)=k mod 13和线性探测处理冲突所得的哈希表a[0..15]:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 01 68 27 55 19 20 84 79 23 11 10
当给定值k=84,则首先和a[6]比在依次和a[7],a[8]比结果a[8]=84查找成功。
当给定值k=38,则首先和a[12]比,再和a[13]比,由于a[13]没有,查找不成功,表中不存在关键字等于38的记
录。
5.5 查找第k小元素
查找第k小元素即在n个元素中(未排序)找到第k小的元素。方法同快速排序,采用递归方式。
程序如下:
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b[s] else
begin
p1:=p(s,t);
q:=p1-s+1;
if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b[i]);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find(1,n,k));
end.
mysqli的异常处理功能?
class check{
private $host;
private $name;
private $paw;
public $res;
function connect($host,$name,$paw){
// var_dump($host,$name,$paw);exit();
$this->res = @new mysqli($host,$name,$paw);
//
if(!$this->res){
throw new Exception("MySQL connect is error!");
}
}
}
try {
$a = new check();
$a->connect("localhost","root","123jodjg");
}catch (Exception $e){
echo $e->getMessage();
}
这个是代码。如果不用mysqli来做。用mysql_connect这样的函数来做就没问题的
php 用户登陆代码,入门教程
function login_xzy()
{
$user_=db("user");
$session_=db("session");
$login['email']=strip_tags($_POST['email']);
$login['pass']=empty($_POST['pass'])?"":md5($_POST['pass']);
if($user=$user_->where("`email`='{$login['email']}' and `pass`='{$login['pass']}'")->find()){
if($session_->where("`uid`='{$user['uid']}'")->find()){
$json['status']=1;
$json['info']='已登陆的会员!';
}else{
$user['total']++;
$user_->where("`uid`='{$user['uid']}'")->update(array('total'=>$user['total'],'lastip'=>ip2long(getip()),'lasttime'=>time() ));
$session_->where("session_id='".Session_id()."'")->update(array('uid'=>$user['uid']));
$_SESSION['user']=$user;
$json['data']=$user;
$json['status']=0;
}
}else{
$json['status']=1;
$json['info']='用户名或密码不正确!';
}
echo json_encode($json);
}
php 用户注册与登陆程序
function islogin_xzy()
{
if(!isset($_SESSION['user'])){
$json['status']=1;
}else{
$ssess_=db("session as s");
$where="s.session_id='".Session_id()."' and u.uid is not null";
if($user=$ssess_->join("`user` as u on u.uid=s.uid")->field("u.*,s.session_id,s.uid")->where($where)->find()){
$json['status']=0;
$json['data']=$user;
}else{
$json['status']=1;
}
}
echo json_encode($json);
}
function reg_xzy()
{
$user_=db("user");
$reg['email']=strip_tags($_POST['email']);
$reg['pass']=empty($_POST['pass'])?"":md5($_POST['pass']);
$reg['sex']=$_POST['sex']=='男' || $_POST['sex']=='女'?$_POST['sex']:'';
$reg['nickname']=strip_tags($_POST['nickname']);
$reg['regip']=ip2long(getip());
$reg['regtime']=time();
$i=0;
foreach($reg as $v){
if(!empty($v)) $i++;
}
if($i!=6){
$json['status']=1;
$json['info']='注册项不全!';
}elseif($user_->where("`email`='{$reg['email']}'")->find()){
$json['status']=1;
$json['info']='已注册的email地址!';
}elseif($uid=$user_->insert($reg)){
$session_=db("session");
$session_->where("session_id='".Session_id()."'")->update(array('uid'=>$uid));
$sessionas_=db("session as s");
$where="s.session_id='".Session_id()."' and s.uid is not null";
if($user=$sessionas_->join("user as u on u.uid=s.uid")->field("u.*,s.session_id,s.uid")->where($where)->find()){
$_SESSION['user']=$user;
$json['data']=$user;
$json['status']=0;
}else{
$json['status']=1;
$json['info']='自动登陆出错,请人工登陆!';
}
}else{
$json['status']=1;
$json['info']='注册失败!';
}
echo json_encode($json);
}
function logout_xzy()
{
$session_=db("session");
$session_->where("session_id='".Session_id()."'")->update(array("uid"=>null));
session_destroy();
}
php 分页代码,支持前10页与后10页分页
function multLink($currentPage, $totalRecords, $url, $pageSize = 10)
{
global $func_message;
if ($totalRecords <= $pageSize) return '';
$mult = '';
$totalPages = ceil($totalRecords / $pageSize);
$mult .= '<div class="pages"><div class="nextprev">';
if ($currentPage > 1)
{
$mult .= '<a href="'.$url.'page='.($currentPage - 1).'">上一页</a>';
}
else
{
$mult .= '<span class="nextprev">上一页</span>';
}
if ($totalPages < 13)
{
for ($counter = 1; $counter <= $totalPages; $counter++)
{
if ($counter == $currentPage)
{
$mult .= '<span class="current">'.$counter.'</span>';
}
else
{
$mult .= '<a href="'.$url.'page='.$counter.'">'.$counter.'</a>';
}
}
}
elseif ($totalPages > 11)
{
if($currentPage < 7)
{
for ($counter = 1; $counter < 10; $counter++)
{
if ($counter == $currentPage)
{
$mult .= '<span class="current">'.$counter.'</span>';
}
else
{
$mult .= '<a href="'.$url.'page='.$counter.'">'.$counter.'</a>';
}
}
$mult .= '<span>…</span><a href="'.$url.'page='.($totalPages-1).'">'.($totalPages-1).'</a><a href="'.$url.'page='.$totalPages.'">'.$totalPages.'</a>';
}
elseif($totalPages - 6 > $currentPage && $currentPage > 6)
{
$mult .= '<a href="'.$url.'page=1">1</a><a href="'.$url.'page=2">2</a><span>…</span>';
for ($counter = $currentPage - 3; $counter <= $currentPage + 3; $counter++)
{
if ($counter == $currentPage)
{
$mult .= '<span class="current">'.$counter.'</span>';
}
else
{
$mult .= '<a href="'.$url.'page='.$counter.'">'.$counter.'</a>';
}
}
$mult .= '<span>…</span><a href="'.$url.'page='.($totalPages-1).'">'.($totalPages-1).'</a><a href="'.$url.'page='.$totalPages.'">'.$totalPages.'</a>';
}
else
{
$mult .= '<a href="'.$url.'page=1">1</a><a href="'.$url.'page=2">2</a><span>…</span>';
for ($counter = $totalPages - 8; $counter <= $totalPages; $counter++)
{
if ($counter == $currentPage)
{
$mult .= '<span class="current">'.$counter.'</span>';
}
else
{
$mult .= '<a href="'.$url.'page='.$counter.'">'.$counter.'</a>';
}
}
}
}
if ($currentPage < $counter - 1)
{
$mult .= '<a href="'.$url.'page='.($currentPage + 1).'" class="nextprev">下一页</a>';
}
else
{
$mult .= '<span class="nextprev">下一页</span>';
}
$mult .= '</div></div>';
return $mult;
}
<br />
.pages {<br />
float:left;<br />
margin:3px 0 5px 10px;<br />
font-size:12px;<br />
}<br />
.pages span.nextprev {<br />
border:1px solid #5CB711;<br />
color:#999999;<br />
}<br />
.pages span.current {<br />
-moz-background-clip:border;<br />
-moz-background-inline-policy:continuous;<br />
-moz-background-origin:padding;<br />
background:#5CB711 none repeat scroll 0 0;<br />
border:1px solid #5CB711;<br />
color:#FFFFFF;<br />
font-weight:bold;<br />
}<br />
.pages a.nextprev {<br />
font-weight:bold;<br />
}<br />
.pages a, .pages a:visited {<br />
border:1px solid #5CB711;<br />
color:#5CB711;<br />
text-decoration:none;<br />
}<br />
.pages a, .pages span {<br />
-moz-background-clip:border;<br />
-moz-background-inline-policy:continuous;<br />
-moz-background-origin:padding;<br />
background:#FFFFFF none repeat scroll 0 0;<br />
display:block;<br />
float:left;<br />
margin-right:0.1em;<br />
padding:0.2em 0.5em;<br />
}<br />
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
同时兼容JS和C#的RSA加密解密算法详解(对web提交的数据加密传输)
这篇文章主要给大家介绍了关于同时兼容JS和C#的RSA加密解密算法,通过该算法可以对web提交的数据进行加密传输,文中通过图文及示例代码介绍的非常详细,需要的朋友们可以参考借鉴,下面来一起看看吧。...2020-06-25- 下面小编就为大家带来一篇Perl与JS的对比分析(数组、哈希)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-29
- 这篇文章主要介绍了JS实现的随机排序功能算法,结合具体实例形式分析了javascript常用的排序算法实现技巧,需要的朋友可以参考下...2017-06-15
- 这篇文章主要介绍了C#常用数据结构和算法,这里我们总结了一些知识点,可以帮助大家理解这些概念。...2020-06-25
- 这篇文章主要介绍了C++实现的O(n)复杂度内查找第K大数算法,结合实例形式分析了算法的原理以及具体实现方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了c# 如何实现位图算法(BitMap),文中讲解非常细致,帮助大家更好的理解和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要给大家介绍了关于Vue虚拟Dom与diff算法的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-08-26
- 在本篇文章里小编给大家整理的是一篇关于R语言关于随机森林算法的知识点详解内容,有兴趣的朋友们可以跟着学习下。...2021-05-13
- 这篇文章主要介绍了C++并查集亲戚(Relations)算法,实例分析了并查集亲戚算法的原理与实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C/C++实现八大排序算法汇总,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 本篇文章介绍了,稀疏图上的Johnson算法的详解。需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了C# URL短地址压缩算法及短网址原理解析,本文重点给出了算法代码,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了VC++实现选择排序算法简单示例,代码简洁易懂,有助于读者对数据结构与算法的学习,需要的朋友可以参考下...2020-04-25
- React 最为核心的就是 Virtual DOM 和 Diff 算法,diff算法的基础是Virtual DOM,接下来通过本文给大家介绍React中diff算法的相关知识,对React中diff算法感兴趣的朋友跟随小编一起学习下吧...2021-05-19
- 在本篇文章里小编给大家整理的是一篇关于php回溯算法计算组合总和的实例代码,有需要的朋友们可以学习参考下。...2021-07-14
- 今天小编就为大家分享一篇关于C#中Hash table的一些操作方法讲解,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧...2020-06-25