程序设计——冲突
前言
程序员们在日常的工作中经常会面临分析需求、原型设计、程序设计、编码实现、测试及部署上线整个流程的其中一个或者多个环节。程序设计可以认为是最重要的环节之一，因为如果没有好的程序设计，所实现的功能必将在可复用性、扩展性、可维护性、可测试性等方面发生问题。本文着重讲解程序设计中最常见的问题——冲突。
什么是冲突？
按照百度百科的解释，冲突包含2个必要因素：1.被双方感知 2.存在意见的对立或不一致，并带有某种相互作用。在日常交通中常常发生机动车、非机动车、行人之间在道路权力上的冲突，比如：
- 通过人行横道的行人与机动车之间的冲突；
- 机动车与非机动车如何划分道路的冲突；
- 直行车辆与转弯车辆之间的冲突。
为了使冲突的双方或者群体有效地完成组织目标和满足个人需要，必须建立群体成员和群体之间的良好和谐关系，即彼此间应互相支持，行动应协调一致。总而言之，需要对冲突进行管理。以上面列出的三种交通冲突为例，《道交法》明确规定了如何妥善管理冲突的三条法规：
- 机动车遇有人行横道，应当减速慢行，甚至停车等待，待行人通过后通行；
- 道路划分机动车道、非机动车道及人行道；
- 规定了转弯让直行，右转让左转等内容。
根据以上内容，冲突发生在人类生活的方方面面，要使社会和谐统一发展就必须对冲突进行管理与协调。在计算机系统中也存在多种多样的冲突，下面我们将逐个介绍。
哈希冲突
哈希表与哈希是计算机系统中最常见的数据结构与算法，对于元素k，通过哈希函数hash(k)就能定位到元素k，其算法复杂度为O(1)，因此广泛应用于计算机系统中。但是直接的哈希有可能将多个元素定位到同一个桶（或者槽）中，这种情况称为哈希冲突。解决哈希冲突通常采用的方法有三种：
- 线性再散列，只简单的按序遍历hash表，寻找下一个可用的槽；
- 非线性再散列，计算一个新的hash值；
- 外部拉链，hash表中的每个槽由具有相同hash值的元素共享，这些元素组成一个链表，链表的头部就是hash表的槽。
线性再散列
线性再散列法是最简单的冲突解决方法。插入元素时，如果发生冲突，算法会简单的遍历hash表，直到找到表中的下一个空槽，并将该元素放入该槽中。查找元素时，首先散列元素所指向的槽，如果没有找到匹配，则继续遍历hash表，直到找到相应的元素或者遍历结束未找到元素。
为简单起见，我们取散列函数h(k)=k mod 10，然后顺序向hash表中插入4、5、7、14、15，如图1所示。
图1 线性再散列法示例
插入4、5和7时由于没有冲突，所以都直接放入槽中；插入14时由于与4发生了槽位的冲突，所以简单遍历空位，最后放入6号槽位中；插入15时与5发生冲突，简单遍历发现6号槽位、7号槽位都已经被占用，因此最终放入了8号槽位。从这个例子看出线性再散列法容易产生哈希聚集（即插入元素几种于某一区域），并且随着插入元素的不断增加，会导致冲突发生频率变高，性能下降甚至不可用。遍历也不是一种好的方法。因此这种方法只适用于数据量不大且槽位中元素可以被清除的情况。
非线性再散列
线性再散列法的线性遍历及元素聚集降低了哈希的性能，为了解决这两个问题，我们可以选择非线性再散列。非线性再散列法通过重新计算一个hash值将元素定位到hash表的其它部分，避免遍历和聚集。如果重新hash到的槽位依然被占用，将继续计算新的hash值。
我们依然接着上面的例子，选择rehash(x)=R-(x mod R)，R是小于哈希表长度10的素数7，那么向表中插入4、5、7、14、15的过程如图2所示。
图2 非线性再散列示例
插入4、5和7时由于没有冲突，所以都直接放入槽中；插入14时由于与4发生了槽位的冲突，所以计算rehash值：7-(14 mod 7)=7，从4号位往后数7位最终放入1号槽；插入15时与5发生冲突，所以计算rehash值：7-(15 mod 7)=6，从5号位往后数6位来到1号位，发现1号位已被14占据，于是再次计算rehash值=6，从1号位往后数6位来到7号位，发现7号位已被7占据，于是再次计算rehash值=6，从7号位往后数6位最终放入3号槽。
非线性再散列法虽然解决了顺序遍历和聚集的问题，但是随着插入元素的不断增加，依然会导致冲突发生频率变高，性能下降甚至不可用。
外部拉链法
解决以上问题的一个方式是将冲突数据放入公共的溢出区，其中最常见的就是将链表链接到每个槽位，这样所以出现冲突的元素比将放入同一个槽位后的链表中。插入4、5、7、14、15等元素后，外部拉链法可以用图3来展示。
图3 外部拉链法
MySQL的自适应哈希索引（AHI）以及Java中的HashMap对冲突都采用了外部拉链法。通过将定位到同一个槽中的元素都放入同一个链表，解决了哈希冲突（由于链表元素的查找性能不高，所有优秀的哈希函数可以产生好的散列，进而降低冲突的可能）。
锁冲突
由于关系型数据库在使用过程中，各个会话中可能会访问共享的表、页、行等数据，因而会产生幻读、不可重复读、脏读等问题，为了保证事务的ACID中的I（隔离性），无论是Oracle、MySQL还是SqlServer都采用了锁这一机制。不同数据库甚至像MySQL这种以存储引擎为核心的数据库，都有各自对于锁的实现。比如Oracle、MySQL的InnoDB存储引擎都实现了表锁、行锁（进一步可以分为共享锁、排它锁及意向锁），而SqlServer实现了页锁、乐观锁及悲观锁等。
以MySQL的InnoDB存储引擎为例，当事务给一行数据加S锁（共享锁）时，其它事务依然可以获取行上的S锁，也就是说多个事务可以并发读取。如果事务给一行数据加了X锁（排它锁），那么其它事务将无法获取行上的S或者X锁。InnoDB存储引擎有个锁等待时间（由参数innodb_lock_wait_timeout控制，默认是50秒），如果超时，等待的事务将退出，这可以防止死锁的发生。退出时还可以根据参数innodb_rollback_on_timeout（默认是OFF，表示不回滚）的设置对事务进行回滚操作。
这里以X锁和S锁的冲突为例，首先我们在一个会话中输入图4中的命令在表t的行上加一个X锁。
图4 获取行X锁
然后在另一个会话中输入图5中的命令在表t的同一行数据上加S锁。
图5 获取行S锁
此时第二个会话加S锁会被阻塞，直到超时退出，如图6所示。
图6 获取行S锁超时退出
数据库在处理事务冲突时为什么不采用类似于外部拉链法的方式，让等待锁的事务在链表中排队呢？如果这些事务都在等待其他事务释放锁，那么这些事务占用的资源及锁也不会得到释放，然后还有更多的事务以滚雪球的方式发生资源或者锁的等待，最终导致所有事务互相等待，甚至死锁造成系统无法正常运行。
临界资源冲突
刚刚谈到数据库的事务冲突，除此之外，数据库还存在临界资源的冲突，比如MySQL数据库的InnoDB存储引擎中的多个线程同时访问内存缓存区中的LRU列表。InnoDB存储引擎处理临界资源冲突的常用方法包括：读写锁、互斥量。Java语言中对于临界资源的处理也与InnoDB非常类似。由于Java线程之间通过加锁或互斥量导致的阻塞，所以Java线程的并发度不是很高，目前广泛采用的方式是基于事件。
游戏冲突
进行游戏开发的同学肯定都知道碰撞检测的重要性。在一副游戏画面中，行进中的主角可能在路线中碰到石头可能会摔倒，主角扔出的石头也会击中怪物。在游戏程序中判断出主角何时碰撞到石头或者石块何时打中怪物都属于碰撞检测。本文从另一个角度将碰撞看做冲突，如果刚才的例子有些牵强的话，那么再举个例子——很多人都见过用不断漂浮的多个气泡所组成的桌面保护程序。每个气泡都沿着自己的方向以不同的速度移动，然后不断与其它气泡发生冲突。发生冲突最好的解决方法就是离开，于是每个气泡似乎都会被其它气泡不断挤开。
游戏领域解决这类冲突的常用方法是将每个对象（如气泡、石头、主角）视为正方形、圆形，计算对象之间的距离判断是否发生了冲突。像气泡、贪吃蛇这类游戏用这种方式处理没有多大问题。一些复杂对象的轮廓也会很复杂，为了提高碰撞检测的准确性就不能将其视为简单的正方形或圆形了。游戏引擎往往提供了成熟的碰撞检测机制，这部分内容有兴趣的读者可以自行了解。
总结
根据以上内容，我们在开发过程中，如果有些逻辑与冲突十分类似，就可以选择本文所述的这些方式来思考。关于冲突的解决方法还有很多，这都需要我们平时的学习和积累。
注意：本文部分内容引用自百度百科。
如需转载，请标明本文作者及出处——作者：jiaan.gja，本文原创首发：博客园，原文链接：http://www.cnblogs.com/jiaan-geng/p/4987917.html
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
